Primitive polynomial (field theory)

• 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), {{nowrap|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 {{nowrap|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 {{nowrap|xⁿ − 1}} is {{nowrap|1=n = p^m − 1}}.
• A primitive polynomial of degree {{mvar|m}} has {{mvar|m}} different roots in {{math|GF(p^m)}}, which all have order {{math|p^m − 1}}, meaning that any of them generates the multiplicative group of the field.
• Over GF(p) there are exactly {{math|φ(p^m − 1)}} primitive elements and {{math|φ(p^m − 1) / m}} primitive polynomials, each of degree {{mvar|m}}, where {{mvar|φ}} is Euler's totient function.Enumerations of primitive polynomials by degree over {{math|GF(2)}}, {{math|GF(3)}}, {{math|GF(5)}}, {{math|GF(7)}}, and {{math|GF(11)}} are given by sequences {{OEIS link|A011260}}, {{OEIS link|A027385}}, {{OEIS link|A027741}}, {{OEIS link|A027743}}, and {{OEIS link|A319166}} in the Online Encyclopedia of Integer Sequences.
• The algebraic conjugates of a primitive element {{mvar|α}} in {{math|GF(p^m)}} are {{mvar|α}}, {{math|α{{i sup|p}}}}, {{math|α{{i sup|p{{sup|2}}}}}}, …, {{math|α{{i sup|p{{sup|m−1}}}}}} and so the primitive polynomial {{math|F(x)}} has explicit form {{math|F(x) {{=}} (x − α) (x − α{{i sup|p}}) (x − α{{i sup|p{{sup|2}}}}) … (x − α{{i sup|p{{sup|m−1}}}})}}. That the coefficients of a polynomial of this form, for any {{mvar|α}} in {{math|GF(pⁿ)}}, not necessarily primitive, lie in {{math|GF(p)}} follows from the property that the polynomial is invariant under application of the Frobenius automorphism to its coefficients (using {{math|α^pn {{=}} α}}) and from the fact that the fixed field of the Frobenius automorphism is {{math|GF(p)}}.

Over {{math|GF(3)}} the polynomial {{math|x² + 1}} is irreducible but not primitive because it divides {{math|x⁴ − 1}}: its roots generate a cyclic group of order 4, while the multiplicative group of {{math|GF(3²)}} is a cyclic group of order 8. The polynomial {{math|x² + 2x + 2}}, on the other hand, is primitive. Denote one of its roots by {{mvar|α}}. Then, because the natural numbers less than and relatively prime to {{math|3² − 1 {{=}} 8}} are 1, 3, 5, and 7, the four primitive roots in {{math|GF(3²)}} are {{mvar|α}}, {{math|α³ {{=}} 2α + 1}}, {{math|α⁵ {{=}} 2α}}, and {{math|α⁷ {{=}} α + 2}}. The primitive roots {{mvar|α}} and {{math|α³}} are algebraically conjugate. Indeed {{math|x² + 2x + 2 {{=}} (x − α) (x − (2α + 1))}}. The remaining primitive roots {{math|α⁵}} and {{math|α⁷ {{=}} (α⁵)³}} are also algebraically conjugate and produce the second primitive polynomial: {{math|x² + x + 2 {{=}} (x − 2α) (x − (α + 2))}}.

For degree 3, {{math|GF(3³)}} has {{math|φ(3³ − 1) {{=}} φ(26) {{=}} 12}} primitive elements. As each primitive polynomial of degree 3 has three roots, all necessarily primitive, there are {{math|12 / 3 {{=}} 4}} primitive polynomials of degree 3. One primitive polynomial is {{math|x³ + 2x + 1}}. Denoting one of its roots by {{mvar|γ}}, the algebraically conjugate elements are {{math|γ³}} and {{math|γ⁹}}. The other primitive polynomials are associated with algebraically conjugate sets built on other primitive elements {{math|γ^r}} with {{mvar|r}} relatively prime to 26:

:

x^3+2x^2+x+1 &= (x-\gamma^5)(x-\gamma^{5\cdot3})(x-\gamma^{5\cdot9}) = (x-\gamma^5)(x-\gamma^{15})(x-\gamma^{19})\\

x^3+x^2+2x+1 &= (x-\gamma^7)(x-\gamma^{7\cdot3})(x-\gamma^{7\cdot9}) = (x-\gamma^7)(x-\gamma^{21})(x-\gamma^{11})\\

x^3+2x^2+1 &= (x-\gamma^{17})(x-\gamma^{17\cdot3})(x-\gamma^{17\cdot9}) = (x-\gamma^{17})(x-\gamma^{25})(x-\gamma^{23}).

\end{align}

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 $\backslash alpha.$ This representation makes multiplication easy, as it corresponds to addition of exponents modulo $p^m-1.$

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 {{nowrap|2ⁿ − 1}}, where n is the length of the linear-feedback shift register) may be built from a primitive polynomial.C. Paar, J. Pelzl - Understanding Cryptography: A Textbook for Students and Practitioners

In general, for a primitive polynomial of degree m over GF(2), this process will generate {{nowrap|2^m − 1}} pseudo-random bits before repeating the same sequence.

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 {{nowrap|2ⁿ − 1}} for a degree n primitive polynomial.

A useful class of primitive polynomials is the primitive trinomials, those having only three nonzero terms: {{nowrap|x^r + x^k + 1}}. Their simplicity makes for particularly small and fast linear-feedback shift registers.{{Cite book |last=Gentle |first=James E. |url=https://www.worldcat.org/oclc/51534945 |title=Random number generation and Monte Carlo methods |date=2003 |publisher=Springer |isbn=0-387-00178-6 |edition=2 |location=New York |pages=39 |oclc=51534945}} A number of results give techniques for locating and testing primitiveness of trinomials.{{Cite journal |last1=Zierler |first1=Neal |last2=Brillhart |first2=John |date=December 1968 |title=On primitive trinomials (Mod 2) |journal=Information and Control |language=en |volume=13 |issue=6 |pages=541, 548, 553 |doi=10.1016/S0019-9958(68)90973-X |doi-access= }}

For polynomials over GF(2), where {{nowrap|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 {{nowrap|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 {{nowrap|x^74207281 + x^30684570 + 1}}.{{cite web |url=https://maths-people.anu.edu.au/~brent/trinom.html |title=Search for Primitive Trinomials (mod 2) |first1=Richard P. |last1=Brent |authorlink1=Richard P. Brent |date=4 April 2016 |access-date=25 May 2024}}{{cite arXiv |title=Twelve new primitive binary trinomials |first1=Richard P. |last1=Brent |authorlink1=Richard P. Brent |first2=Paul |last2=Zimmermann |authorlink2=Paul Zimmermann (mathematician) |eprint=1605.09213 |class=math.NT |date=24 May 2016 }} This can be used to create a pseudo-random number generator of the huge period {{nowrap|2^74207281 − 1}} ≈ {{val|3|e=22338617}}.

{{reflist}}

• {{MathWorld |urlname=PrimitivePolynomial |title=Primitive Polynomial}}

Category:Field (mathematics)

Category:Polynomials