# 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(p$^m$). 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(p$^m$) such that $\{0,1,\alpha ,\alpha ^{2},\alpha ^{3},\ldots \alpha ^{p^{m}-2}\}$ is the entire field GF(p$^m$). This implies that α is a primitive (p$^m$ − 1)-root of unity in GF(p$^m$).

## 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 x$^n$ − 1 is n = p$^m$ − 1.
* A primitive polynomial of degree m has m different roots in GF(p$^m$), which all have order p$^m$ − 1, meaning that any of them generates the multiplicative group of the field.
* Over GF(p) there are exactly φ(p$^m$ − 1) primitive elements and φ(p$^m$ − 1) / m primitive polynomials, each of degree m, where φ is Euler's totient function.
* The algebraic conjugates of a primitive element α in GF(p$^m$) 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(p$^n$), 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 x$^2$ + 1 is irreducible but not primitive because it divides x$^4$ − 1: its roots generate a cyclic group of order 4, while the multiplicative group of GF(3$^2$) is a cyclic group of order 8. The polynomial x$^2$ + 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 3$^2$ − 1 = 8 are 1, 3, 5, and 7, the four primitive roots in GF(3$^2$) are α, α$^3$ = 2α + 1, α$^5$ = 2α, and α$^7$ = α + 2. The primitive roots α and α$^3$ are algebraically conjugate. Indeed x$^2$ + 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: x$^2$ + x + 2 = (x − 2α) (x − (α + 2)).
For degree 3, GF(3$^3$) has φ(3$^3$ − 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 x$^3$ + 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:
    ${\begin{aligned}x^{3}+2x+1&=(x-\gamma )(x-\gamma ^{3})(x-\gamma ^{9})\\x^{3}+2x^{2}+x+1&=(x-\gamma ^{5})(x-\gamma ^{5\cdot 3})(x-\gamma ^{5\cdot 9})=(x-\gamma ^{5})(x-\gamma ^{15})(x-\gamma ^{19})\\x^{3}+x^{2}+2x+1&=(x-\gamma ^{7})(x-\gamma ^{7\cdot 3})(x-\gamma ^{7\cdot 9})=(x-\gamma ^{7})(x-\gamma ^{21})(x-\gamma ^{11})\\x^{3}+2x^{2}+1&=(x-\gamma ^{17})(x-\gamma ^{17\cdot 3})(x-\gamma ^{17\cdot 9})=(x-\gamma ^{17})(x-\gamma ^{25})(x-\gamma ^{23}).\end{aligned}}$

## Applications
### Field element representation

Primitive polynomials can be used to represent the elements of a finite field. If α in GF(p$^m$) is a root of a primitive polynomial F(x), then the nonzero elements of GF(p$^m$) are represented as successive powers of α:
    $\mathrm {GF} (p^{m})=\{0,1=\alpha ^{0},\alpha ,\alpha ^{2},\ldots ,\alpha ^{p^{m}-2}\}.$
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 $\alpha .$ This representation makes multiplication easy, as it corresponds to addition of exponents modulo $p^{m}-1.$

### Pseudo-random bit generation

Primitive polynomials over GF(2), the field with two elements, can be used for pseudorandom bit generation. In fact, every linear-feedback shift register with maximum cycle length (which is 2$^n$ − 1, where n is the length of the linear-feedback shift register) may be built from a primitive polynomial.
In general, for a primitive polynomial of degree m over GF(2), this process will generate 2$^m$ − 1 pseudo-random bits before repeating the same sequence.

### CRC codes

The cyclic redundancy check (CRC) is an error-detection code that operates by interpreting the message bitstring as the coefficients of a polynomial over GF(2) and dividing it by a fixed generator polynomial also over GF(2); see Mathematics of CRC. Primitive polynomials, or multiples of them, are sometimes a good choice for generator polynomials because they can reliably detect two bit errors that occur far apart in the message bitstring, up to a distance of 2$^n$ − 1 for a degree n primitive polynomial.

## Primitive trinomials

A useful class of primitive polynomials is the primitive trinomials, those having only three nonzero terms: x$^r$ + x$^k$ + 1. Their simplicity makes for particularly small and fast linear-feedback shift registers. A number of results give techniques for locating and testing primitiveness of trinomials.
For polynomials over GF(2), where 2$^r$ − 1 is a Mersenne prime, a polynomial of degree r is primitive if and only if it is irreducible. (Given an irreducible polynomial, it is not primitive only if the period of x is a non-trivial factor of 2$^r$ − 1. Primes have no non-trivial factors.) Although the Mersenne Twister pseudo-random number generator does not use a trinomial, it does take advantage of this.
Richard Brent has been tabulating primitive trinomials of this form, such as x$^{74207281}$ + x$^{30684570}$ + 1. This can be used to create a pseudo-random number generator of the huge period 2$^{74207281}$ − 1 ≈ 3×10$^{22338617}$.