Primitive Trinomial of Record Degree
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
We are pleased to announce a new primitive trinomial of record degree 6972593.
The trinomial, over the finite field GF(2), is
(A) x^6972593 + x^3037958 + 1
It was found on 31 August 2002 on a Sparc Ultra-80 in Oxford.
The previous record degree (by the same authors, in August 2000)
was achieved with the trinomial
(B) x^3021377 + x^361604 + 1
The degree 6972593 is the exponent of a Mersenne prime M6972593. Thus,
in order to show that (A) is primitive, it suffices to show that it is
irreducible. This takes 16 hours on a 500 Mhz Pentium III with our program
"irred". The method is described in:
R. P. Brent, S. Larvala and P. Zimmermann, "A fast algorithm for testing
reducibility of trinomials mod 2 and some new primitive trinomials of
degree 3021377", Mathematics of Computation, to appear. Preprint available
from http://www.comlab.ox.ac.uk/oucl/work/richard.brent/pub/pub199.html
Because the trinomial (A) is primitive, the associated linear recurrence
(C) x[n] = x[n-6972593] + x[n-3037958] (mod 2)
has period M6972593 = 2^6972593 - 1. This leads to random number generators
with extremely large period and good statistical properties.
One larger Mersenne prime (M13466917 = 2^13466917 - 1) is known
(see http://www.mersenne.org/status.htm). It is easy to show, using
Swan's theorem, that there are no primitive trinomials of degree 13466917.
We have now completed 53% of a complete search for primitive trinomials
of degree 6972593. The search commenced in February 2001 and has taken about
100,000 mips-years so far. Further information on the search for primitive
and "almost primitive" trinomials (that is, trinomials which have a large
primitive factor) is available at
http://www.comlab.ox.ac.uk/oucl/work/richard.brent/trinom.html
We are grateful to the following individuals and organisations for their
assistance in providing computer time:
Nate Begeman
Nicolas Daminelli
Brendan McKay
Barry Mead
Juan Varona
Australian National University Supercomputer Facility (ANUSF)
Australian Partnership for Advanced Computing (APAC)
Centre Informatique National de l'Enseignement Superieur (CINES)
INRIA Lorraine
Oxford Centre for Computational Finance (OCCF)
Oxford Supercomputing Centre (OSC)
Oxford University Computing Laboratory (OUCL)
Richard P. Brent
Samuli Larvala
Paul Zimmermann
3 September 2002