A Fast Algorithm for Testing Irreducibility of Trinomials mod 2 - Archive ouverte HAL Access content directly
Reports Year : 2000

A Fast Algorithm for Testing Irreducibility of Trinomials mod 2

(1) , (1) , (2)
1
2

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.
Not file

Dates and versions

inria-00099332 , version 1 (26-09-2006)

Identifiers

  • HAL Id : inria-00099332 , version 1

Cite

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⟩
58 View
0 Download

Share

Gmail Facebook Twitter LinkedIn More