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