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.
Type de document :
Rapport
[Intern report] A00-R-465 || brent00a, 2000, 13 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00099332
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:52:59
Dernière modification le : jeudi 11 janvier 2018 - 06:20:00

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

115