Skip to Main content Skip to Navigation

A Fast Algorithm for Testing Irreducibility of Trinomials mod 2

Richard P. Brent 1 Samuli Larvala 1 Paul Zimmermann 2
2 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The standard algorithm for testing reducibility of a trinomial of prime % this assumption avoids GCD test for divisors of the degree degree $r$ over \GF(2) requires $2r + O(1)$ bits of memory and $\Theta(r^2)$ bit-operations. We describe an algorithm which requires only $3r/2 + O(1)$ bits of memory and significantly fewer bit-operations than the standard algorithm. Using the algorithm, we have found 18 new irreducible trinomials of degree $r$ in the range $100151 \le r \le 700057$. If $r$ is a Mersenne exponent (i.e.~$2^r-1$ is a Mersenne prime), then an irreducible trinomial is primitive. Primitive trinomials are of interest because they can be used to give pseudo-random number generators with period at least $2^r-1$. We give examples of primitive trinomials for $r = 756839$, $859433$, and $3021377$. The three results for $r = 756839$ are new. The results for $r = 859433$ extend and correct some computations of Kumada {\etal} [{\em{Math. Comp.}} 69 (2000), 811--814]. The two results for $r = 3021377$ are primitive trinomials of the highest known degree.
Document type :
Complete list of metadatas
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:52:59 AM
Last modification on : Friday, October 16, 2020 - 4:02:02 PM


  • HAL Id : inria-00099332, version 1



Richard P. Brent, Samuli Larvala, Paul Zimmermann. A Fast Algorithm for Testing Irreducibility of Trinomials mod 2. [Intern report] A00-R-465 || brent00a, 2000, 13 p. ⟨inria-00099332⟩



Record views