Algorithms for finding almost irreducible and almost primitive trinomials

212. R. P. Brent and P. Zimmermann, Algorithms for finding almost irreducible and almost primitive trinomials, in Primes and Misdemeanours: Lectures in Honour of the Sixtieth Birthday of Hugh Cowie Williams (edited by A. van der Poorten and A. Stein), Fields Institute Communication FIC/41, The Fields Institute, Toronto, published by the American Mathematical Society, 2004, 91-102. Invited paper presented at a conference in Banff, Canada, May 2003.

Preprint: dvi (28K), pdf (242K), ps (84K).

Overhead Transparencies (for the Banff talk): dvi (14K), pdf (224K), ps (144K).


Consider polynomials over GF(2). We describe efficient algorithms for finding trinomials with large irreducible (and possibly primitive) factors, and give examples of trinomials having a primitive factor of degree r for all Mersenne exponents r = +3 mod 8 for r the range (5, 107), although there is no irreducible trinomial of degree r. We also give trinomials with a primitive factor of degree r =2k for 3 <= k <= 12. These trinomials enable efficient representations of the finite fields GF(2r). We show how trinomials with large primitive factors can be used efficiently in applications where primitive trinomials would normally be used.


This paper extends the algorithm of [199] to "almost irreducible" and "almost primitive" trinomials. See [211] for an application to random number generators.

A related talk (presented at ECCAD03, Clemson) on Primitive and Almost Primitive Trinomials over GF(2) is available here.

See the online description for the current status of the search for almost primitive trinomials.

Go to next publication

Return to Richard Brent's index page