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 (to appear in AMS Notices).

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

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.

More details are available here.

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.

- 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*^{880890}+ 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*^{55981}+ 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).

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

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 August 2013