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^{7}, 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.
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.
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.
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.
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).
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.
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.
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.
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^{2}), 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.
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