Editing Primitive polynomial (field theory)

{{Short description|Minimal polynomial of a primitive element in a finite field}}
{{For|polynomials such that the greatest common divisor of the coefficients is 1|Primitive polynomial (ring theory)}}
{{Use American English|date = March 2019}}
{{More citations needed|date=May 2010}}
In [[field theory (mathematics)|finite field theory]], a branch of [[mathematics]], a '''primitive polynomial''' is the [[minimal polynomial (field theory)|minimal polynomial]] of a [[primitive element (finite field)|primitive element]] of the [[finite field]] {{math|GF(''p''<sup>''m''</sup>)}}. This means that a polynomial {{math|''F''(''X'')}} of degree {{mvar|m}} with coefficients in {{math|1=GF(''p'') = '''Z'''/''p'''''Z'''}} is a ''primitive polynomial'' if it is [[monic polynomial|monic]] and has a root {{math|''α''}} in {{math|GF(''p''<sup>''m''</sup>)}} such that <math>\{0,1,\alpha, \alpha^2,\alpha^3,  \ldots \alpha^{p^m-2}\}</math> is the entire field {{math|GF(''p''<sup>''m''</sup>)}}. This implies that {{math|''α''}} is a [[primitive root of unity|primitive ({{math|''p''<sup>''m''</sup> − 1}})-root of unity]] in {{math|GF(''p''<sup>''m''</sup>)}}.

==Properties==
* Because all minimal polynomials are [[irreducible polynomial|irreducible]], all primitive polynomials are also irreducible.
* A primitive polynomial must have a non-zero constant term, for otherwise it will be divisible by&nbsp;''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''<sup>''n''</sup> − 1}} is {{nowrap|1=''n'' = ''p''<sup>''m''</sup> − 1}}.
* A primitive polynomial of degree {{mvar|m}} has {{mvar|m}} different roots in {{math|GF(''p''<sup>''m''</sup>)}}, which all have [[order (group theory)|order]] {{math|''p''<sup>''m''</sup> − 1}}, meaning that any of them generates the [[Finite field#Multiplicative structure|multiplicative group]] of the field.
* Over GF(''p'') there are exactly {{math|''φ''(''p''<sup>''m''</sup> − 1)}} primitive elements and {{math|''φ''(''p''<sup>''m''</sup> − 1) / ''m''}} primitive polynomials, each of degree {{mvar|m}}, where {{mvar|φ}} is [[Euler's totient function]].<ref>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]].</ref>
* The [[Conjugate element (field theory)|algebraic conjugates]] of a primitive element {{mvar|α}} in {{math|GF(''p''<sup>''m''</sup>)}} 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''<sup>''n''</sup>)}}, 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|''α''<sup>''p''<sup>''n''</sup></sup> {{=}} ''α''}}) and from the fact that the fixed field of the Frobenius automorphism is {{math|GF(''p'')}}.

==Examples==
Over {{math|GF(3)}} the polynomial {{math|''x''<sup>2</sup> + 1}} is irreducible but not primitive because it divides {{math|''x''<sup>4</sup> − 1}}: its roots generate a cyclic group of order 4, while the multiplicative group of {{math|GF(3<sup>2</sup>)}} is a cyclic group of order 8. The polynomial {{math|''x''<sup>2</sup> + 2''x'' + 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<sup>2</sup> − 1 {{=}} 8}} are 1, 3, 5, and 7, the four primitive roots in {{math|GF(3<sup>2</sup>)}} are {{mvar|α}}, {{math|''α''<sup>3</sup> {{=}} 2''α'' + 1}}, {{math|''α''<sup>5</sup> {{=}} 2''α''}}, and {{math|''α''<sup>7</sup> {{=}} ''α'' + 2}}. The primitive roots {{mvar|α}} and {{math|''α''<sup>3</sup>}} are algebraically conjugate. Indeed {{math|''x''<sup>2</sup> + 2''x'' + 2 {{=}} (''x'' − ''α'') (''x'' − (2''α'' + 1))}}. The remaining primitive roots {{math|''α''<sup>5</sup>}} and {{math|''α''<sup>7</sup> {{=}} (''α''<sup>5</sup>)<sup>3</sup>}} are also algebraically conjugate and produce the second primitive polynomial: {{math|''x''<sup>2</sup> + ''x'' + 2 {{=}} (''x'' − 2''α'') (''x'' − (''α'' + 2))}}.

For degree 3, {{math|GF(3<sup>3</sup>)}} has {{math|''φ''(3<sup>3</sup> − 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''<sup>3</sup> + 2''x'' + 1}}. Denoting one of its roots by {{mvar|γ}}, the algebraically conjugate elements are {{math|''γ''<sup>3</sup>}} and {{math|''γ''<sup>9</sup>}}. The other primitive polynomials are associated with algebraically conjugate sets built on other primitive elements {{math|''γ''<sup>''r''</sup>}} with {{mvar|r}} relatively prime to 26:
:<math>\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\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}</math>

==Applications==
===Field element representation===
Primitive polynomials can be used to represent the elements of a [[finite field]].  If ''α'' in GF(''p''<sup>''m''</sup>) is a root of a primitive polynomial ''F''(''x''), then the nonzero elements of GF(''p''<sup>''m''</sup>) are represented as successive powers of ''α'':

:<math>
\mathrm{GF}(p^m) = \{ 0, 1= \alpha^0, \alpha, \alpha^2, \ldots, \alpha^{p^m-2} \} .
</math>

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 <math>\alpha.</math> This representation makes multiplication easy, as it corresponds to addition of exponents [[modular arithmetic|modulo]] <math>p^m-1.</math>

===Pseudo-random bit generation===
Primitive polynomials over GF(2), the field with two elements, can be used for [[Pseudorandom number generator|pseudorandom bit generation]]. In fact, every [[linear-feedback shift register]] with maximum cycle length (which is {{nowrap|2<sup>''n''</sup> − 1}}, where ''n'' is the length of the linear-feedback shift register) may be built from a primitive polynomial.<ref>C. Paar, J. Pelzl - Understanding Cryptography: A Textbook for Students and Practitioners</ref>

In general, for a primitive polynomial of degree ''m'' over GF(2), this process will generate {{nowrap|2<sup>''m''</sup> − 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 {{nowrap|2<sup>''n''</sup> − 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: {{nowrap|''x<sup>r</sup>'' + ''x<sup>k</sup>'' + 1}}.  Their simplicity makes for particularly small and fast [[linear-feedback shift register]]s.<ref>{{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}}</ref>  A number of results give techniques for locating and testing primitiveness of trinomials.<ref>{{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= }}</ref>

For polynomials over GF(2), where {{nowrap|2<sup>''r''</sup> − 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<sup>''r''</sup> − 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 (scientist)|Richard Brent]] has been tabulating primitive trinomials of this form, such as {{nowrap|''x''<sup>74207281</sup> + ''x''<sup>30684570</sup> + 1}}.<ref>{{cite web |url=https://maths-people.anu.edu.au/~brent/trinom.html |title=Search for Primitive Trinomials (mod&nbsp;2) |first1=Richard P. |last1=Brent |authorlink1=Richard P. Brent |date=4 April 2016 |access-date=25 May 2024}}</ref><ref>{{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 <!-- unsupported parameter |url=https://maths-people.anu.edu.au/~brent/pd/rpb266.pdf -->}}</ref> This can be used to create a pseudo-random number generator of the huge period {{nowrap|2<sup>74207281</sup> − 1}} ≈ {{val|3|e=22338617}}.

==References==
{{reflist}}

==External links==
* {{MathWorld |urlname=PrimitivePolynomial |title=Primitive Polynomial}}

[[Category:Field (mathematics)]]
[[Category:Polynomials]]