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