## 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, 10^{7}),
although there is no irreducible trinomial of degree *r*.
We also give
trinomials with a primitive factor of degree
*r* =2^{k} for
3 <= *k* <= 12.
These trinomials enable efficient
representations of the finite fields GF(2^{r}).
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