Search for Primitive Trinomials (mod 2)

Consider polynomials over the finite field GF(2) of two elements {0, 1}.

A polynomial with only three nonzero terms is called a trinomial.

An irreducible polynomial is one which has no nontrivial (polynomial) factors. A primitive polynomial is one which is irreducible and satisfies another technical condition. For the precise definition, see our papers [199, 212].

For each primitive trinomial, there is another with s replaced by r-s, so we can assume that s < r / 2.

In general, to test if a trinomial is primitive, we need to know the prime factorisation of M_r = 2^r - 1. Testing primitivity is particularly easy if M_r is a Mersenne prime, i.e. r is a Mersenne exponent. In this special case, the trinomial is primitive if and only if it is irreducible. In the following, we assume that r is a Mersenne exponent.

By a theorem of Swan, it is easy to rule out Mersenne exponents r if r = 3 or 5 (mod 8). For the remaining known Mersenne exponents r less than 10⁷, at least one primitive trinomial with degree r r is known, and a plausible argument suggests that the average number is about 3.2 per exponent.

Application - Random Number Generators

Uniform random number generators with extremely long periods can easily be implemented if we can find polynomials

x^r + x^s + 1, 0 < s < r

which are primitive over GF(2). The random number generators use a linear recurrence defined by the polynomial. Trinomials give very efficient random number generators because the associated linear recurrence has only three terms. For more information on such "Generalized Fibonacci" random number generators, see the papers Uniform random number generators for supercomputers and Random number generators with period divisible by a Mersenne prime. An implementation of such random number generators is available here.

A New Algorithm for Testing Irreducibility of Trinomials over GF(2)

We have developed a new algorithm which is significantly faster than the standard algorithm for testing irreducibility of trinomials with prime degree. For details, see our paper in Mathematics of Computation 72 (2003), 1443-1452.

Examples

If r = 756839, then s = 279695 gives a primitive trinomial

x⁷⁵⁶⁸³⁹ + x²⁷⁹⁶⁹⁵ + 1
This was discovered by the author on 9 June 2000, and can be verified in seven minutes on a 500 Mhz IBM PC.
Other primitive trinomials discovered recently by the author with the same r have s = 215747 and 267428.
If r = 859433, then s = 288477 gives a primitive trinomial

x⁸⁵⁹⁴³³ + x²⁸⁸⁴⁷⁷ + 1
This was discovered by Kumada et al: see Mathematics of Computation 69 (2000), 811-814. It can be verified in ten minutes on a 500 Mhz IBM PC.
If r = 859433, then s = 170340 gives a primitive trinomial

x⁸⁵⁹⁴³³ + x¹⁷⁰³⁴⁰ + 1
This was found by the author on 26 June 2000. It was missed by Kumada et al due to a bug in their sieve program, but has now been verified by Kumada et al (and independently by M. Yoder).
If r = 3021377, then s = 361604 gives a primitive trinomial "Hodgkin":

x^3021377 + x³⁶¹⁶⁰⁴ + 1
Hodgkin was discovered by the author (in collaboration with Samuli Larvala and Paul Zimmermann) on 8 August 2000. Using our program, primitivity can be verified in two hours on a 500 Mhz IBM PC (P-III processor with 512KB L2 cache). It has been verified with an independent program by M. Yoder.
The nickname Hodgkin comes from the fact that I was reading a fascinating biography of Dorothy Hodgkin by Georgina Ferry when the trinomial was found.
If r = 3021377, then s = 1010202 gives a primitive trinomial "Erin":

x^3021377 + x^1010202 + 1
Erin was discovered by the author (in collaboration with Samuli Larvala and Paul Zimmermann) on 17 December 2000. It has been verified with an independent program by M. Yoder.
If r = 6972593, then s = 3037958 gives a primitive trinomial "Bibury":

x^6972593 + x^3037958 + 1
Bibury was discovered by the author, in collaboration with Samuli Larvala and Paul Zimmermann, on 31 August 2002. On that afternoon, while our program was running on a Sparc Ultra-80 processor at the Oxford Centre for Computational Finance, the three of us we were visiting the lovely village of Bibury in Gloucestershire (not far from Oxford); hence the nickname.
Irreducibility has been verified with Victor Shoup's NTL package. The verification took 13 hours on an 833Mhz Alpha EV68, using version 5.3 of NTL compiled with gcc 2.95.3 (version 3.11 of our program irred takes 4 hours 20 minutes on the same machine). Irreducibility has also been checked with versions of our program running on several different machines (using both 32-bit and 64-bit arithmetic, and both the "new" and "standard" algorithms).
Of all known primitive polynomials, Bibury has the largest degree (in fact the degree is more than twice as large as the next largest, which are Erin and Hodgkin). This means that Bibury gives random number generator with the longest period and is, in a sense, the current "world record" primitive trinomial.
From the known primitive trinomials of degree 6972593 (Bibury and its reciprocal), we can deduce infinite families of irreducible trinomials whose degrees are multiples of 2^6972593 - 1 .

Search Status

In collaboration with Samuli Larvala and Paul Zimmermann, I performed a search for r = 756839. (Three primitive trinomials were found, see above).

We have also completed a verification of published results for all Mersenne exponents r < 3021377. (One new primitive trinomial was found for r = 859433, see above). A summary of the computational results may be found here.

From 11 July 2000 to 2 April 2001 we searched for primitive trinomials with r = 3021377. The time to check one trinomial is O(r²), so the search took about 43 times longer than that for r = 859433. There were r/2 = 1,510,688 possible s trinomials to check. Sieving discards trinomials which have low-degree factors (our sieve limit was usually degree 24 or 25). Most (92.77%) of the trinomials were eliminated quickly by sieving. The remaining 109,245 trinomials each took about two hours to check on a 500 Mhz Pentium III. On a single 500 Mhz processor the search would have taken about 27 years. Of course, we used as many processors as we could find (including assorted IBM PCs, Sparcs and Alphas) running in parallel, so the search for r = 3021377 was completed in less than nine months (about 13,400 Mips-years). Exactly two new primitive trinomials were found (see Hodgkin and Erin above). Details of the computation are given in our paper A fast algorithm for testing reducibility of trinomials mod 2 ...

On 6 February 2001 we started a search with the next Mersenne exponent, r = 6972593. Most (93.22%) of the trinomials were eliminated by sieving, leaving 236,245 "hard" cases. A hard case takes about 15 hours on a 500 Mhz Pentium III and about 3.6 hours on a 1Ghz Alpha ES45. The search was completed on 25 July 2003, using an estimated 230,000 Mips-years of computer time (about 17 times longer than the search for exponent 3021377). One primitive trinomial (Bibury) was found. Further details are available in our preprint A primitive trinomial of degree 6972593.

The Program irred

A program irred is available as open-source software under the GNU General Public License. It is written in C with optional assembler routines for IBM PCs, and runs under Linux, Solaris or other flavours of Unix (not yet Windows). Information on how to download the source code for irred is available here.

Log Files

A log file is a list of triples (r, s, status) indicating which trinomials have been tested and the result. Details are available here, and a list of known errors is available here.

An Extension - "Almost Primitive" Trinomials

In cases where r is a Mersenne exponent but no primitive trinomial of degree r exists, we are searching for trinomials of slightly higher degree which have a primitive factor of degree r. Such trinomials are called "almost primitive". Blake, Gao and Lambert (unpublished) found almost primitive trinomials for r < 500; we have extended their computations and have found at least one (primitive or) "almost primitive" trinomial for each Mersenne exponent less than 10⁷. The results for almost primitive trinomials are given here. A preprint Algorithms for finding almost irreducible and almost primitive trinomials is available.

Checking our Results

Our new primitive and "almost primitive" trinomials have been checked using the NTL package, and also (where feasible) the Magma package. Mike Yoder also checked some of our results with his independently written Ada program.

However, it is conceivable that an undetected hardware or software problem caused us to miss a primitive or "almost primitive" trinomial. To be sure that this is not the case, someone should perform our computations again, using an independently-written program, and compare the results obtained with our log files. Although a discrepancy is unlikely, it is certainly possible, as past experience with long computations shows (see above).

On 8 October 2003 we completed a verification of the results for degree 3021377 by rerunning our program irred on different machines with (in some cases) different sieving limits. No errors were found.

We have checked a subset of the results for degrees 3021377 and 6972593, using Victor Shoup's NTL package in addition to our own program irred.

The verification for degree 3021377 was completed on 23 March 2007. The extended log for degree 3021377 (excluding the two primitive trinomials) has been verified using Magma.

The verification for degree 6972593 was completed on 30 April 2007. The extended log for degree 6972593 (excluding one primitive trinomial) has been verified using Magma.

Some errors were found in the original log file for degree 6972593. These errors have now been corrected. Fortunately they do not change the results concerning primitive trinomials. Details of the checks and errors found are available here.

R. P. Brent

(in collaboration with Samuli Larvala and Paul Zimmermann; with assistance from Nate Begeman, Nicolas Daminelli, Philippe Falandry, Shuhong Gao, Brendan McKay, Ernst Mayer, Barry Mead, Mark Rodenkirch, Julian Seward, Victor Shoup, Allan Steel, Andrew Tridgell, Juan Luis Varona, George Woltman and Mike Yoder)

20 September 2002