Programming Research Group Technical Report TR-13-00

A fast algorithm for testing irreducibility of trinomials mod 2

Richard Brent, S. Larvala and P. Zimmerman

December 2000, 16pp.

Abstract

The standard algorithm for testing irreducibility of a trinomial of degree r over GF(2) requires 2r + O(1) bits of memory and of order r2 bit-operations. We describe an algorithm which requires only 3r/2 + O(1) bits of memory and less bit-operations than the standard algorithm. Using the algorithm, we have found several new irreducible trinomials of high degree.

If r is a Mersenne exponent (i.e. 2r - 1 is a Mersenne prime), then an irreducible trinomial of degree r is necessarily primitive and can be used to give a pseudo-random number generator with period at least 2r - 1. We give examples of primitive trinomials for 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.

This paper is available as a 104026 bytes gzipped PostScript file.