In field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite field GF(pm). This means that a polynomial F(X) of degree m with coefficients in GF(p) = Z/pZ is a primitive polynomial if it is monic and has a root α in GF(pm) such that { 0 , 1 , α , α 2 , α 3 , … α p m − 2 } {\displaystyle \{0,1,\alpha ,\alpha ^{2},\alpha ^{3},\ldots \alpha ^{p^{m}-2}\}} is the entire field GF(pm). This implies that α is a primitive (pm − 1)-root of unity in GF(pm).
Properties Because all minimal polynomials are irreducible, all primitive polynomials are also irreducible. A primitive polynomial must have a non-zero constant term, for otherwise it will be divisible by x. Over GF(2), x + 1 is a primitive polynomial and all other primitive polynomials have an odd number of terms, since any polynomial mod 2 with an even number of terms is divisible by x + 1 (it has 1 as a root). An irreducible polynomial F(x) of degree m over GF(p), where p is prime, is a primitive polynomial if the smallest positive integer n such that F(x) divides xn − 1 is n = pm − 1. A primitive polynomial of degree m has m different roots in GF(pm), which all have order pm − 1, meaning that any of them generates the multiplicative group of the field. Over GF(p) there are exactly φ(pm − 1) primitive elements and φ(pm − 1) / m primitive polynomials, each of degree m, where φ is Euler's totient function. The algebraic conjugates of a primitive element α in GF(pm) are α, αp, αp2, …, αpm−1 and so the primitive polynomial F(x) has explicit form F(x) = (x − α) (x − αp) (x − αp2) … (x − αpm−1). That the coefficients of a polynomial of this form, for any α in GF(pn), not necessarily primitive, lie in GF(p) follows from the property that the polynomial is invariant under application of the Frobenius automorphism to its coefficients (using αpn = α) and from the fact that the fixed field of the Frobenius automorphism is GF(p).
Examples Over GF(3) the polynomial x2 + 1 is irreducible but not primitive because it divides x4 − 1: its roots generate a cyclic group of order 4, while the multiplicative group of GF(32) is a cyclic group of order 8. The polynomial x2 + 2x + 2, on the other hand, is primitive. Denote one of its roots by α. Then, because the natural numbers less than and relatively prime to 32 − 1 = 8 are 1, 3, 5, and 7, the four primitive roots in GF(32) are α, α3 = 2α + 1, α5 = 2α, and α7 = α + 2. The primitive roots α and α3 are algebraically conjugate. Indeed x2 + 2x + 2 = (x − α) (x − (2α + 1)). The remaining primitive roots α5 and α7 = (α5)3 are also algebraically conjugate and produce the second primitive polynomial: x2 + x + 2 = (x − 2α) (x − (α + 2)). For degree 3, GF(33) has φ(33 − 1) = φ(26) = 12 primitive elements. As each primitive polynomial of degree 3 has three roots, all necessarily primitive, there are 12 / 3 = 4 primitive polynomials of degree 3. One primitive polynomial is x3 + 2x + 1. Denoting one of its roots by γ, the algebraically conjugate elements are γ3 and γ9. The other primitive polynomials are associated with algebraically conjugate sets built on other primitive elements γr with r relatively prime to 26:
… excerpt ends here. Continue reading the full article.
