Search for Primitive Trinomials (mod 2)

See my old trinomial page for an introduction to trinomials over GF(2) and some history.

For a summary and the history of the search, see The Great Trinomial Hunt.

A summary of the primitive trinomials for known Mersenne exponents is here.

Certificates

Certificates are available for degrees 1279, 2281, 3217, 4423, 9689, 19937, 23209, 44497, 110503, 132049, 756839, 859433, 3021377, 6972593, 24036583, 25964951, 30402457, 32582657, 42643801, 43112609, 57885161, 74207281.

More details are available here.

How to check a certificate?

Alternatively, download the check-ntl.c file, compile it with NTL, and run check-ntl 32582657 < i32582657.log-ext (for example). The check-ntl program is much faster for large exponents than the check.magma program.

Status of new Mersenne exponents

• r=13466917 (M39): ruled out by Swan theorem since r=5 (mod 8), and x^r+x^2+1 is divisible by x^2+x+1.


• r=20996011 (M40): ruled out by Swan theorem since r=3 (mod 8), and x^r+x^2+1 is divisible by x^2+x+1.


• r=24036583 (M41): search started on April 25, 2007, completed on August 27, 2007: there are exactly two primitive trinomials (with their reciprocal) which have been checked by Allan Steel using Magma:
  x^24036583 + x^8785528 + 1   (Judy-anne),          x^24036583 + x^8412642 + 1   (Eugénie),


• r=25964951 (M42): search started on July 19, 2007, completed on November 3, 2007: there are exactly four primitive trinomials (with their reciprocal) which have been checked by Allan Steel using Magma:
  x^25964951 + x⁸⁸⁰⁸⁹⁰ + 1 (T25a),    x^25964951 + x^4627670 + 1 (T25b),    x^25964951 + x^4830131 + 1 (T25c),    x^25964951 + x^6383880 + 1   (Nancy).


• r=30402457 (M43?): search started on October 22, 2007, completed on December 12, 2007: there is exactly one primitive trinomial (with its reciprocal), which has been checked by Allan Steel using Magma:
  x^30402457 + x^2162059 + 1 (Florence).


• r=32582657 (M44?): search started on November 30, 2007, completed on January 24, 2008: there are exactly three primitive trinomials (with their reciprocals), which have been checked by Allan Steel using Magma:
  x^32582657 + x^5110722 + 1 (Priscilla),    x^32582657 + x^5552421 + 1 (T32b),    x^32582657 + x^7545455 + 1 (T33c).
• r=37156667 (M45?): ruled out by Swan's theorem since r=3 mod 8, and x^r+x^2+1 is divisible by x^5+x^2+1.

• r=42643801 (M46?): search started on June 18, 2009, completed 31 August 2009.

  Five primitive trinomials found -
  

  x^42643801 + x⁵⁵⁹⁸¹ + 1,   (T42a)
  x^42643801 + x^3706066 + 1,   (T42b)
  x^42643801 + x^3896488 + 1,   (T42c)
  x^42643801 + x^12899278 + 1,   (T42d)
  x^42643801 + x^20150445 + 1.   (T42e)

• r=43112609 (M47?): search started on September 18, 2008, completed 8 May 2009.

  Four primitive trinomials found -
  

  x^43112609 + x^3569337 + 1,   (T43a)
  x^43112609 + x^4463337 + 1,   (T43b)
  x^43112609 + x^17212521 + 1,   (T43c)
  x^43112609 + x^21078848 + 1.   (T43d)
  

• r=57885161 (M48?): search started on 9 February 2013, completed 13 May 2013 (with assistance from Bill Hart and Alex Kruppa).

  No primitive trinomials found
  

• r=74207281 (M49?): search started on 25 January 2016, completed 25 March 2016.

  Three primitive trinomials found -
  

  x^74207281 + x^9156813 + 1,   (T44a)
  x^74207281 + x^9999621 + 1,   (T44b)
  x^74207281 + x^30684570 + 1.   (T44c)
  

Software

• Download the gf2x package. gf2x is a C/C++ software package containing routines for fast arithmetic in GF(2)[x] (multiplication, squaring, GCD) and searching for irreducible/primitive trinomials.
  
  
• Download irred-ntl-1.9. This is a patch for NTL, (version 5.3.1 or 5.3.2), which speeds up the multiplication over GF(2)[x], in particular by implementing Toom-Cook's 3-way algorithm. With NTL 5.4, download irred-ntl-1.9-5.4. These files are distributed under the terms of the GNU General Public License.

Further Information

See my old trinomial page for some history, and also Paul Zimmermann's page.

Richard Brent (in collaboration with Paul Zimmermann,
with CPU cycles contributed by Dan Bernstein, Bill Hart and Tanja Lange)

Last revised 4 April 2016.

Return to Richard Brent's index page