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 :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00099332
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:52:59 AM
Last modification on : Thursday, January 11, 2018 - 6:20:00 AM

Identifiers

  • HAL Id : inria-00099332, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

124