Editing Primitive polynomial (field theory) (section)

==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}}.