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