A Fast Algorithm for Testing Irreducibility of Trinomials mod 2
Résumé
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.