Search for Primitive Trinomials (mod 2)

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

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

Certificates

A certificate is simply a list of smallest irreducible factors for trinomials of given degree r. In our certificates the factors are encoded in hexadecimal.

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

More details are available here,

How to check a certificate?

First download the certificate, uncompress it (gunzip ixxx.log-ext.gz), download the check.magma program, replace the value of r and the file name in the first lines, then start Magma and type:
load "check.magma";

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

Status of new Mersenne exponents (those larger than 6972593):

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, x^25964951 + x^4627670 + 1, x^25964951 + x^4830131 + 1, 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.

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, x^32582657 + x^5552421 + 1, x^32582657 + x^7545455 + 1.

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=43112609 (M46?): search started on September 18, 2008, completed 8 May 2009. The certificates will be available soon.
Four primitive trinomials found -

x^43112609 + x^3569337 + 1,
x^43112609 + x^4463337 + 1,
x^43112609 + x^17212521 + 1,
x^43112609 + x^21078848 + 1.

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

A paper is available here.

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 and Tanja Lange)

Last revised 8 May 2009

Return to Richard Brent's index page