Primitive polynomial (field theory)

Template:Short description Template:For Template:Use American English Template:More citations needed In finite field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite field Template:Math. This means that a polynomial Template:Math of degree Template:Mvar with coefficients in Template:Math is a primitive polynomial if it is monic and has a root Template:Math in Template:Math such that $\{0,1,\alpha ,{\alpha }^2,{\alpha }^3,\dots {\alpha }^{p^m-2}\}$ is the entire field Template:Math. This implies that Template:Math is a [[primitive root of unity|primitive (Template:Math)-root of unity]] in Template:Math.

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), Template:Nowrap 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 Template:Nowrap (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 Template:Nowrap is Template:Nowrap.
• A primitive polynomial of degree Template:Mvar has Template:Mvar different roots in Template:Math, which all have order Template:Math, meaning that any of them generates the multiplicative group of the field.
• Over GF(p) there are exactly Template:Math primitive elements and Template:Math primitive polynomials, each of degree Template:Mvar, where Template:Mvar is Euler's totient function.
• The algebraic conjugates of a primitive element Template:Mvar in Template:Math are Template:Mvar, Template:Math, Template:Math, …, Template:Math and so the primitive polynomial Template:Math has explicit form Template:Math. That the coefficients of a polynomial of this form, for any Template:Mvar in Template:Math, not necessarily primitive, lie in Template:Math follows from the property that the polynomial is invariant under application of the Frobenius automorphism to its coefficients (using Template:Math) and from the fact that the fixed field of the Frobenius automorphism is Template:Math.

Examples

Over Template:Math the polynomial Template:Math is irreducible but not primitive because it divides Template:Math: its roots generate a cyclic group of order 4, while the multiplicative group of Template:Math is a cyclic group of order 8. The polynomial Template:Math, on the other hand, is primitive. Denote one of its roots by Template:Mvar. Then, because the natural numbers less than and relatively prime to Template:Math are 1, 3, 5, and 7, the four primitive roots in Template:Math are Template:Mvar, Template:Math, Template:Math, and Template:Math. The primitive roots Template:Mvar and Template:Math are algebraically conjugate. Indeed Template:Math. The remaining primitive roots Template:Math and Template:Math are also algebraically conjugate and produce the second primitive polynomial: Template:Math.

For degree 3, Template:Math has Template:Math primitive elements. As each primitive polynomial of degree 3 has three roots, all necessarily primitive, there are Template:Math primitive polynomials of degree 3. One primitive polynomial is Template:Math. Denoting one of its roots by Template:Mvar, the algebraically conjugate elements are Template:Math and Template:Math. The other primitive polynomials are associated with algebraically conjugate sets built on other primitive elements Template:Math with Template:Mvar relatively prime to 26:

$\begin{array}{cc}{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{array}$

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{G}\mathrm{F}(p^m)=\{0,1={\alpha }^0,\alpha ,{\alpha }^2,\dots ,{\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 Template:Nowrap, 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 Template:Nowrap 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 Template:Nowrap for a degree n primitive polynomial.

Primitive trinomials

A useful class of primitive polynomials is the primitive trinomials, those having only three nonzero terms: Template:Nowrap. 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 Template:Nowrap 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 Template:Nowrap. 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 Template:Nowrap. This can be used to create a pseudo-random number generator of the huge period Template:Nowrap ≈ Template:Val.

External links

• Template:MathWorld