Table of primitive trinomials x^r + x^s + 1 (mod 2)
Note: We assume that 0 < 2s < r (so x^r + x^(r-s) + 1 is not listed)
and that r is a Mersenne exponent (i.e. 2^r - 1 prime).
For definitions see Knuth, Volume 2, third edition, Sec. 3.2.2.
For entries up to 9941, see N. Zierler, Inform. Control 15 (1969), 67.
For entries up to r = 216091, see J. W. Heringa et al,
"New primitive trinomials of Mersenne-exponent degrees
for random-number generation", International Journal of
Modern Physics C 3 (1992), 561-564.
The three entries with r = 756839 were found by R. Brent, 9-14 June 2000.
The first entry with r = 859433 was found by R. Brent, 26 June 2000.
For the second entry with r = 859433, see Kumada et al, Math. Comp. 69 (2000),
811-814.
The search for r = 3021377 by Brent, Larvala and Zimmermann
was started in July 2000 and completed on 2 April 2001.
The entry with r = 6972593 was found by Brent, Larvala and Zimmermann
on 31 August 2002 when 53% of the search had been completed.
The search for r = 6972593 was completed on 25 July 2003.
A search for r = 24036583 was started on 25 April 2007 and completed on
27 August 2007.
A search for r = 25964951 was started on 18 July 2007 and completed on
4 November 2007.
A search for r = 30402457 was started on 22 October 2007 and completed on
12 Dec 2007.
A search for r = 32582657 was started on 30 Nov 2007 and completed on
11 Feb 2008.
A search for r = 43112609 was started on 18 Sept 2008 and completed on
8 May 2009.
A search for r = 42643801 was started on 18 June 2009 and completed on
31 August 2009.
A search for r = 57885161 was started on 9 Feb 2013 and by 3 April 2013
it had been found that there is no primitive trinomial of this degree.
A search for r = 74207281 was started on 25 Jan 2016 and completed on
1 April 2016.
Note that entries with r = +- 3 mod 8 are unlikely, since s = 2 (or r-2)
is then the only possibility, by Swan's theorem. The only cases known
are r = 3 and r = 5.
r s Notes
2 1 Only even r
3 1 Only known case r = 3 (mod 8)
5 2 Only known case r = 5 (mod 8)
7 1, 3
13 -
17 3, 5, 6
19 -
31 3, 6, 7, 13
61 -
89 38
107 -
127 1, 7, 15, 30, 63
521 32, 48, 158, 168
607 105, 147, 273
1279 216, 418
2203 -
2281 715, 915, 1029
3217 67, 576
4253 -
4423 271, 369, 370, 649, 1393, 1419, 2098
9689 84, 471, 1836, 2444, 4187
9941 - Limit of Zierler's tables
11213 -
19937 881, 7083, 9842
21701 -
23209 1530, 6619, 9739
44497 8575, 21034
86243 -
110503 25230, 53719
132049 7000, 33912, 41469, 52549, 54454
216091 - Limit of Heringa's tables
756839 215747 Brent, 14 June 2000
756839 267428 Brent, 11 June 2000
756839 279695 Brent, 9 June 2000
859433 170340 Brent, 26 June 2000
859433 288477 Kumada et al
1257787 - Kumada et al
1398269 - Kumada et al
2976221 - Kumada et al
3021377 361604 Brent et al, 8 August 2000 (Hodgkin)
3021377 1010202 Brent et al, 17 Dec 2000 (Erin)
6972593 3037958 Brent et al, 31 August 2002 (Bibury)
13466917 - See note (1) below
20996011 - See note (2) below
24036583 8412642 Brent & Zimmermann, 4 July 2007 (Eugenie)
24036583 8785528 Brent & Zimmermann, 27 June 2007 (Judy-anne)
See note (3) below
25964951 880890 Brent & Zimmermann, 20 Oct 2007 (T25a)
25964951 4627670 Brent & Zimmermann, 19 Oct 2007 (T25b)
25964951 4830131 Brent & Zimmermann, 19 Oct 2007 (T25c)
25964951 6383880 Brent & Zimmermann, 17 Oct 2007 (Nancy)
See note (4) below
30402457 2162059 Brent & Zimmermann, 28 Nov 2007 (Florence)
See note (5) below
32582657 5110722 Brent & Zimmermann, 24 Jan 2008 (Priscilla)
32582657 5552421 Brent & Zimmermann, 30 Jan 2008 (T32b)
32582657 7545455 Brent & Zimmermann, 24 Jan 2008 (T32c)
See note (6) below
37156667 - See note (7) below
42643801 55981 Brent & Zimmermann, 21 July 2009
42643801 3706066 Brent and Zimmermann, 10 Aug 2009
42643801 3896488 Brent and Zimmermann, 10 Aug 2009
42643801 12899278 Brent and Zimmermann, 26 July 2009
42643801 20150445 Brent and Zimmermann, 13 July 2009
See note (8) below
43112609 3569337 BBLZ 20090103
43112609 4463337 BBLZ 20090103
43112609 17212521 BBLZ 20090301
43112609 21078848 BBLZ 20081022
See note (9) below
57885161 none See note (10) below, BHKZ
74207281 9156813 BZ 20160320
74207281 9999621 BZ 20160320
74207281 30684570 BZ 20160320
See note (11) below
Notes
(1) (21 December 2001): the Mersenne exponent r = 13466917 can be ruled out.
r = 5 mod 8, so by Swan's theorem we only need consider s = 2. In this case
the trinomial (considered over GF(2)) is divisible by x^2 + x + 1; this is
easy to verify as r = 1 mod 3.
(2) (2 December 2003): the Mersenne exponent r = 20996011 can be ruled out.
r = 3 mod 8, so by Swan's theorem we only need consider s = 2. In this case
the trinomial (considered over GF(2)) is divisible by x^2 + x + 1; this is
easy to verify as r = 1 mod 3.
(3) (19 May 2004): the Mersenne exponent r = 24036583 has r = -1 mod 8
so we can't rule out a primitive trinomial of this degree by Swan's theorem.
If the search time is of order r^3 we expect about 41 times as long as
for r = 6972593. However, our new program "factor" is about 430 times
faster than irred.
Postscript (25 April 2007): We are starting to search for a primitive
trinomial with this exponent, using our improved program which has expected
search time of order r^(2+epsilon) and is faster than the old program by
a factor of more than 300 for this exponent.
Postscript (27 June 2007): Primitive trinomial found for s = 8785528,
confirmed with irred (twice).
Postscript (4 July 2007): Primitive trinomial found for s = 8412642,
confirmed with irred (twice).
Postscript (27 Aug 2007): Search for r = 24036583 completed.
(4) (28 February 2005): the Mersenne exponent r = 25964951 has r = -1 mod 8
so can not be ruled out by Swan's theorem. Search started 18 July 2007.
Postscript (20 Oct 2007): Four primitive trinomials found 17-20 Oct 2007,
The search was completed 4 Nov 2007.
(5) (20 December 2005): the Mersenne exponent r = 30402457 has r = +1 mod 8
so can not be ruled out by Swan's theorem. Search started on bogong
22 Oct 2007 and a little later on the Grid 5000. One primitive trinomial
found 28 Nov 2007. Search completed 12 Dec 2007.
(6) (5 September 2006): the Mersenne exponent r = 32582657 has r = +1 mod 8
so can not be ruled out by Swan's theorem. Search started 30 Nov 2007.
By 30 Jan 2008 we had found 3 primitive trinomials and determined that no
others (excepting reciprocals of these three) are primitive. Certificates
completed 11 Feb 2008, verification of primitives by Allan Steel 20 Feb 2008.
Postscript (17 September 2008): Two new Mersenne primes were announced by
the GIMPS project in September 2008 - see notes (7) and (9) below.
(7) (17 September 2008): the Mersenne exponent r = 37156667 can be ruled out.
r = 3 mod 8, so by Swan's theorem we only need consider s = 2. In this case
the trinomial (considered over GF(2)) is divisible by x^5 + x^2 + 1; this is
easy to verify as r = 5 mod 31 and x^5 + x^2 + 1 is an irreducible factor
of x^31 - 1.
(8) (14 June 2009): the Mersenne exponent r = 42643801 was recently
announced by the GIMPS project (found out of order). A search for
primitive trinomials with this exponent commenced 18 June 2009.
42643801 55981 (20090721, T42a)
42643801 3706066 (20090810, T42b)
42643801 3896488 (20090810, T42c)
42643801 12899278 (20090726, T42d)
42643801 20150445 (20090713. T42e)
Search completed 31 August 2009.
(9) (17 September 2008): the Mersenne exponent r = 43112609 has r = +1 mod 8
so can not be ruled out by Swan's theorem. We plan to search for primitive
trinomials of degree r using the same algorithm that was used for degree
32582657 (with a possible improvement in the irreducibility test).
BBLZ = Richard Brent, Dan Bernstein, Tanja Lange and Paul Zimmermann.
22 Oct 2008: found s = 21078848 search 4% complete (T43a)
3 Jan 2009: found s = 3569337 search 40% complete (T43b)
3 Jan 2009: found s = 4463337 search 40% complete (T43c)
1 Mar 2009: found s = 17212521 search 85% complete (T43d)
8 May 2009: search 100% complete.
(10) Mersenne prime 57885161 found 25 Jan. 2013. r = +1 mod 8 so can not
be ruled out by Swan's theorem.
BHKZ = RB (Richard Brent) + WH (Bill Hart) + AK (Alex Kruppa) +
PZ (Paul Zimmermann)
PZ and AK started runs 9 Feb 2013, RPB started runs 23 Feb 2013.
Reduced to 0 candidates (with 16 not yet factored) by 3 April 2013.
All factored by 13 May 2013. The two with "largest smallest" factors
were completely factored by 24 August 2013.
(11) Mersenne prime 74207281 found 7 Jan. 2016. r = +1 mod 8. RPB and PZ
started factor/irred runs 25 Jan 2016 and finished 4 April 2016. Verified
using Magma program 4 April 2016 (this uncovered a possible bug in Magma's
implementation of quotient rings).