A fast algorithm for testing reducibility

199. 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 72 (2003), 1443-1452 (posted electronically 18 Dec 2002). MR 1 972 745.

Also "A fast algorithm for testing irreducibility of trinomials mod 2 (preliminary report)", Report PRG TR-13-00, 30 December 2000.

Preprint: dvi (24K), pdf (343K), ps (73K).

Preliminary Report: dvi (27K), pdf (208K), ps (100K).


The standard algorithm for testing irreducibility of a trinomial of prime degree r over GF(2) requires 2r + O(1) bits of memory. We describe an algorithm which requires only 3r/2 + O(1) bits of memory and 44 percent of the number of bit-operations required by the standard algorithm.

If  2r - 1 is a Mersenne prime, then an irreducible trinomial of degree r is necessarily primitive. We give primitive trinomials for the Mersenne exponents r = 756839, 859433, and 3021377. The results for r = 859433 extend and correct some computations of Kumada et al [Mathematics of Computation 69 (2000), 811-814]. The two results for r = 3021377 are primitive trinomials of the highest known degree.


The preliminary report was written when the search for primitive trinomials of degree r = 3021377 was about 60 percent completed. The two new primitive trinomials of degree 3021377 are

x3021377 + x361604 + 1    and    x3021377 + x1010202 + 1.

On 31 August 2002 we found a larger primitive trinomial, of degree 6972593. For further details see [214, 230].

For an extension to "almost irreducible" and "almost primitive" trinomials, see [212]. A talk on Primitive and Almost Primitive Trinomials over GF(2) is available here.

For the application to random number generators, see [132, 211].

Go to next publication

Return to Richard Brent's index page