There is no primitive trinomial of degree 57885161 over GF(2)
=============================================================

On January 25th 2013, GIMPS found a new Mersenne prime 2^57885161-1 [1].

On February 6 2013, we started a search for primitive trinomials of degree
57885161 over GF(2), following the search done for previous Mersenne
exponents found by GIMPS [2].

This search was completed on May 13 2013. The unexpected result is that there
is no primitive trinomial of degree 57885161 over GF(2). Indeed, for each
integer s, 1 <= s <= 57885161/2, we were able to find a non-trivial factor
of x^57885161 + x^s + 1. Those factors are given in the certificate file [3],
which can be checked using the check-ntl program available on [2].

For each trinomial, we found a factor of smallest degree. The largest such
(smallest) degree is 7777044, for s=6341306.

This search was done with our implementation of the algorithm from [4]
(see [5] for a more high-level description), using the GF2X software tool [6].

For this search, we used a client-server architecture designed by Alexander
Kruppa, which simplified a lot the distribution of task to the computers
available. Computing resources were provided by the Mathematical Sciences
Institute of the Australian National University, and by the Caramel team
at Inria Nancy Grand-Est/LORIA. We also credit Bill Hart's EPSRC grant
EP/G004870/1 at Warwick University.

Richard Brent
Bill Hart
Alexander Kruppa
Paul Zimmermann

[1] http://mersenne.org/various/57885161.htm
[2] http://webloria.loria.fr/~zimmerma/irred/
[3] http://webloria.loria.fr/~zimmerma/irred/i57885161.log-ext.bz2
[4] http://maths-people.anu.edu.au/~brent/pub/pub230.html
[5] http://maths-people.anu.edu.au/~brent/pub/pub235.html
[6] http://gf2x.gforge.inria.fr/