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).
Abstract
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.
Comments
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