## 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).

## Abstract

The standard algorithm for testing irreducibility of a trinomial of
prime degree *r* over GF(2) requires 2*r* + O(1)
bits of memory.
We describe an algorithm which requires only 3*r*/2 + O(1)
bits of memory and 44 percent of the number of
bit-operations required by the standard algorithm.
If 2^{r} - 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.

## Comments

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

*x*^{3021377} + *x*^{361604} + 1
and
*x*^{3021377} + *x*^{1010202} + 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