Primitive polynomial (field theory)

In finite 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 is the entire field GF(pm). This implies that α is a primitive (pm − 1)-root of unity in GF(pm). 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. Over GF(p) there are exactly φ(pm − 1)/m primitive polynomials of degree m, where φ is Euler's totient function. A primitive polynomial of degree m has m different roots in GF(pm), which all have order pm − 1. This means that, if α is such a root, then α^p^m−1 = 1 and α^i ≠ 1 for 0 < i < pm − 1. The primitive polynomial F(x) of degree m of a primitive element α in GF(pm) has explicit form F(x) = (x − α)(x − α^p)(x − α^p^2)⋅⋅⋅(x − α^p^m−1). Primitive polynomials can be used to represent the elements of a finite field. If α in GF(pm) is a root of a primitive polynomial F(x), then the nonzero elements of GF(pm) are represented as successive powers of α: This allows an economical representation in a computer of the nonzero elements of the finite field, by representing an element by the corresponding exponent of This representation makes multiplication easy, as it corresponds to addition of exponents modulo Primitive polynomials over GF(2), the field with two elements, can be used for pseudorandom bit generation.