Irreducible polynomials over Zp
Recall (Definition 2.190) that a polynomial f(x) e Z_{p}[x] of degree m > 1 is said to be irreducible over Z_{p} if it cannot be written as a product of two polynomials in Z_{p}[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 F_{p}m = Z_{p}[x]/(f(x)), the set of all polynomials in Z_{p}[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 Z_{p}, where p is a prime. The characteristic two finite fields F_{2}m 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 Z_{2}.
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 Z_{p}[x for which ж is a generator of F*m, the multiplicative group of the finite field F_{p}... = Z_{p}[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 Z_{p}[x] is irreducible over Z_{?)} and a is a non-zero element in Z_{p}, then a- f(x) is also irreducible over Z_{p}. Hence it suffices to restrict attention to monic polynomials in Z_{p}[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 Z_{2}[x], then its constant term must be 1.
There is a formula for computing exactly the number of monic irreducible polynomials in Z_{p}[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 N_{p}(m) of monic irreducible polynomials of degree m in Z_{p}[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 Z_{p} [x] being irr educible over Z_{p} is roughly T. More specifically, the number N_{p}(m) satisfies
Testing irreducibility of polynomials in Z_{p}[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 Z_{p}[x of degree dividing к is equal to x^{pk} - x.
- (ii) Let f(x) be a polynomial of degree m in Z_{p}[x). Then /(x) is irreducible over Z_{p} if and only if gcd(/(x), x^{p}' - 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 Z_{p}[x.
OUTPUT: an answer to the question: “Is /(x) irreducible over Z_{P}T
- 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 Z_{p}[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 Z_{p}[x] is to generate a random monic polynomial of degree m in Z_{p}[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 Z_{p }INPUT: a prime p and a positive integer m.
OUTPUT: a monic irreducible polynomial /(ж) of degree m in Z_{p}[x}.
- 1. Repeat the following:
- 1.1 (Generate a random monic polynomial of degree m in Z_{p}[x])
Randomly select integers ao, «i, «2, ■ • • , ^{a}m-i between 0 and p— 1 with ao ф
- 0. Let f(x) be the polynomial /(ж) = x^{m} +a_{m}-x^{m}~^{* l} ------l-a2X^{2}+aia;+oo.
- 1.2 Use Algorithm 4.69 to test whether /(ж) is irreducible over Z_{p}.
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 Z_{p}[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)m^{2}) Z_{p}-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(m^{3}(lgm)(lgp)) Z_{p}-operations.
Given one irreducible polynomial of degree m over Z_{p}, 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 F_{4}. A minimum polynomial of q over Z_{p} is a monic polynomial of least degree in Z_{p}[x having a as a root.
- 4.73 Fact Let F,, be a finite field of order q = p^{m}, and let a e F_{9}.
The minimum polynomial of a over Z_{p}, denoted m_{a}(r), is unique.
- (ii) m_{a}(x) is irreducible over Z_{p}.
- (iii) The degree of rn_{a}(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, a^{p}"' = 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 Z_{p}. The finite field F_{p}.« can then be represented as F_{p}m = Z_{p}y]/(f(y)). A random monic irreducible polynomial of degree m over Z_{p} can be efficiently generated as follows. First generate a random element a e F_{p}m and then, by repeated exponentiation by p, determine the smallest positive integer t for which a^{p} = a. If t < m, then generate a new random element a € F_{p}m and repeat; the probability that t < m is known to be at most (lg m)/q^{m}I^{2}. If indeed t = m, then compute m_{a}(x) using the formula (4.1). Then m_{a}(x) is a random monic irreducible polynomial of degree m in Z_{p} [ж]. This method has an expected running time of О (in^{3} (lg;;)) Z_{p}-operations (compare with Fact 4.71).