Primitive polynomial (field theory) explained

In finite field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite field . This means that a polynomial of degree with coefficients in is a primitive polynomial if it is monic and has a root in such that

\{ 0 , 1 ,\alpha, \alpha ^{2,\alpha} ^{3,} \ldots \alpha ^{p ^{m-2}} \} is the entire field . This implies that is a primitive -root of unity in .

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

Examples

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

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

\begin{align}x ^{3+2x+1} & = (x - \gamma)(x - \gamma ^{3)(x-\gamma} ^{9)\\ x} ^{3+2x} ^{2+x+1} & = (x - \gamma ^{5)(x-\gamma} ^{5 ⋅ 3} )(x - \gamma ^{5 ⋅ 9} ) = (x - \gamma ^{5)(x-\gamma} ^{15} )(x - \gamma ^{19} )\\ x ^{3+x} ^{2+2x+1} & = (x - \gamma ^{7)(x-\gamma} ^{7 ⋅ 3} )(x - \gamma ^{7 ⋅ 9} ) = (x - \gamma ^{7)(x-\gamma} ^{21} )(x - \gamma ^{11} )\\ x ^{3+2x} ^{2+1} & = (x - \gamma ^{17} )(x - \gamma ^{17 ⋅ 3} )(x - \gamma ^{17 ⋅ 9} ) = (x - \gamma ^{17} )(x - \gamma ^{25} )(x - \gamma ^{23} ). \end{align}

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 α:

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, where n is the length of the linear-feedback shift register) may be built from a primitive polynomial.^[2]

In general, for a primitive polynomial of degree m over GF(2), this process will generate 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 for a degree n primitive polynomial.

Primitive trinomials

A useful class of primitive polynomials is the primitive trinomials, those having only three nonzero terms: . Their simplicity makes for particularly small and fast linear-feedback shift registers.^[3] A number of results give techniques for locating and testing primitiveness of trinomials.^[4]

For polynomials over GF(2), where 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 . 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 .^{[5] [6]} This can be used to create a pseudo-random number generator of the huge period ≈ .

Notes and References

1. Enumerations of primitive polynomials by degree over,,,, and are given by sequences,,,, and in the Online Encyclopedia of Integer Sequences.
2. C. Paar, J. Pelzl - Understanding Cryptography: A Textbook for Students and Practitioners
3. Book: Gentle, James E. . Random number generation and Monte Carlo methods . 2003 . Springer . 0-387-00178-6 . 2 . New York . 39 . 51534945.
4. Zierler . Neal . Brillhart . John . December 1968 . On primitive trinomials (Mod 2) . Information and Control . en . 13 . 6 . 541, 548, 553 . 10.1016/S0019-9958(68)90973-X .
5. Web site: Search for Primitive Trinomials (mod 2) . Richard P. . Brent . Richard P. Brent . 4 April 2016 . 25 May 2024.
6. --> Twelve new primitive binary trinomials . Richard P. . Brent . Richard P. Brent . Paul . Zimmermann . Paul Zimmermann (mathematician) . 1605.09213 . math.NT . 24 May 2016 .