 Irreducible polynomials over Zp

Recall (Definition 2.190) that a polynomial f(x) e Zp[x] of degree m > 1 is said to be irreducible over Zp if it cannot be written as a product of two polynomials in Zp[x] each having degree less than m. Such a polynomial f(x) can be used to represent the elements of the finite field F;,™ as Fpm = Zp[x]/(f(x)), the set of all polynomials in Zp[x] of degree less than m where the addition and multiplication of polynomials is performed modulo f(x) (see §2.6.3). This section presents techniques for constructing irreducible polynomials over Zp, where p is a prime. The characteristic two finite fields F2m are of particular interest for ciyptographic applications because the arithmetic in these fields can be efficiently performed both in software and in hardware. For this reason, additional attention is given to the special case of irreducible polynomials over Z2.

The arithmetic in finite fields can usually be implemented more efficiently if the irreducible polynomial chosen has few non-zero terms. Irreducible trinomials, i.e., irreducible polynomials having exactly three non-zero terms, are considered in §4.5.2. Primitive polynomials, i.e., irreducible polynomials f(x) of degree m in Zp[x for which ж is a generator of F*m, the multiplicative group of the finite field Fp... = Zp[x]/(f(x)) (Definition 2.228), are the topic of §4.5.3. Primitive polynomials are also used in the generation of linear feedback shift register sequences having the maximum possible period (Fact 6.12).

Irreducible polynomials

If f(x) e Zp[x] is irreducible over Z?) and a is a non-zero element in Zp, then a- f(x) is also irreducible over Zp. Hence it suffices to restrict attention to monic polynomials in Zp[x],

i.e., polynomials whose leading coefficient is 1. Observe also that if f(x) is an irreducible polynomial, then its constant term must be non-zero. In particular, if f(x) e Z2[x], then its constant term must be 1.

There is a formula for computing exactly the number of monic irreducible polynomials in Zp[x] of a fixed degree. The Mobius function, which is defined next, is used in this formula.

4.65 Definition Let m be a positive integer. The Mobius function // is defined by 4.66 Example (Mobius function) The following table gives the values of the Mobius function ц{т) for the first 10 values of m:

 m 1 2 3 4 5 6 7 8 9 10 p(m) 1 -1 -1 0 -1 1 -1 0 0 1

• 4.67 Fact (number ofmonic irreducible polynomials) Let p be a prime and m a positive integer.
• (i) The number Np(m) of monic irreducible polynomials of degree m in Zp[x] is given by the following formula: where the summation ranges over all positive divisors d of m.

(ii) The probability of a random monic polynomial of degree m in Zp [x] being irr educible over Zp is roughly T. More specifically, the number Np(m) satisfies Testing irreducibility of polynomials in Zp[x is significantly simpler than testing pri- mality of integers. A polynomial can be tested for irreducibility by verifying that it has no irreducible factors of degree < Ly J ■ The following result leads to an efficient method (Algorithm 4.69) for accomplishing this.

• 4.68 Fact Let p be a prime and let к be a positive integer.
• (i) The product of all monic irreducible polynomials in Zp[x of degree dividing к is equal to xpk - x.
• (ii) Let f(x) be a polynomial of degree m in Zp[x). Then /(x) is irreducible over Zp if and only if gcd(/(x), xp' - x) = 1 for each г, 1 < i < |_?rj.
• 4.69 Algorithm Testing a polynomial for irreducibility

INPUT: a prime p and a monic polynomial /(x) of degree m in Zp[x.

OUTPUT: an answer to the question: “Is /(x) irreducible over ZPT

• 1. Set u(x)<— x.
• 2. For i from 1 to |_yj do the following:
• 2.1 Compute u(x)<-u(x)p mod f(x) using Algorithm 2.227. (Note that u(x) is a polynomial in Zp[x] of degree less than m.)
• 2.2 Compute d(x) = gcd(/(x), u(x) - x) (using Algorithm 2.218).
• 2.3 If d(x) ф 1 then retum(“reducible”).
• 3. Retum(“irreducible”).

Fact 4.67 suggests that one method for finding an irreducible polynomial of degree m in Zp[x] is to generate a random monic polynomial of degree m in Zp[x, test it for irreducibility, and continue until an irreducible one is found (Algorithm 4.70). The expected number of polynomials to be tried before an irreducible one is found is approximately m.

4.70 Algorithm Generating a random monic irreducible polynomial over Zp INPUT: a prime p and a positive integer m.

OUTPUT: a monic irreducible polynomial /(ж) of degree m in Zp[x}.

• 1. Repeat the following:
• 1.1 (Generate a random monic polynomial of degree m in Zp[x])

Randomly select integers ao, «i, «2, ■ • • , am-i between 0 and p— 1 with ao ф

• 0. Let f(x) be the polynomial /(ж) = xm +am-xm~* l ------l-a2X2+aia;+oo.
• 1.2 Use Algorithm 4.69 to test whether /(ж) is irreducible over Zp.

Until f(x) is irreducible.

2. Retum(/(ж)).

It is known that the expected degree of the irreducible factor of least degree of a random polynomial of degree m in Zp[x] is 0(lg m). Hence for each choice of f{x), the expected number of times steps 2.1 - 2.3 of Algorithm 4.69 are iterated is 0(lg m). Each iteration takes 0((lgp)m2) Zp-operations. These observations, together with Fact 4.67(ii), determine the running time for Algorithm 4.70.

4.71 Fact Algorithm 4.70 has an expected running time of 0(m3(lgm)(lgp)) Zp-operations.

Given one irreducible polynomial of degree m over Zp, Note 4.74 describes a method, which is more efficient than Algorithm 4.70, for randomly generating additional such polynomials.

• 4.72 Definition Let IF,, be a finite field of characteristic p, and let a e F4. A minimum polynomial of q over Zp is a monic polynomial of least degree in Zp[x having a as a root.
• 4.73 Fact Let F,, be a finite field of order q = pm, and let a e F9.

The minimum polynomial of a over Zp, denoted ma(r), is unique.

• (ii) ma(x) is irreducible over Zp.
• (iii) The degree of rna(x) is a divisor of m.
• (iv) Let t be the smallest positive integer such that e/ = a. (Note that such a t exists since, by Fact 2.213, ap"' = a.) Then 4.74 Note (generating new irreducible polynomials from a given one) Suppose that f(y) is a given irreducible polynomial of degree m over Zp. The finite field Fp.« can then be represented as Fpm = Zpy]/(f(y)). A random monic irreducible polynomial of degree m over Zp can be efficiently generated as follows. First generate a random element a e Fpm and then, by repeated exponentiation by p, determine the smallest positive integer t for which ap = a. If t < m, then generate a new random element a € Fpm and repeat; the probability that t < m is known to be at most (lg m)/qmI2. If indeed t = m, then compute ma(x) using the formula (4.1). Then ma(x) is a random monic irreducible polynomial of degree m in Zp [ж]. This method has an expected running time of О (in3 (lg;;)) Zp-operations (compare with Fact 4.71).