A Fast Algorithm for Testing Reducibility of Trinomials mod 2 and Some New Primitive Trinomials of Degree 3021377

Richard P. Brent 1 Samuli Larvala 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 degree $r$ over $\GF(2)$ requires $2r + O(1)$ bits of memory. We describe a new algorithm which requires only $3r/2 + O(1)$ bits of memory and significantly fewer memory references and bit-operations than the standard algorithm. If $2^r-1$ is a Mersenne prime, then an irreducible trinomial of degree $r$ is necessarily primitive. We give primitive trinomials for the Mersenne exponents $r = 756839$, $859433$, and $3021377$. % The results for $r = 859433$ extend and correct some computations of Kumada {\etal}. The two results for $r = 3021377$ are primitive trinomials of the highest known degree.
Type de document :
Article dans une revue
Mathematics of Computation, American Mathematical Society, 2003, 72 (243), pp.1443-1452
Liste complète des métadonnées

https://hal.inria.fr/inria-00099744
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 09:40:51
Dernière modification le : jeudi 11 janvier 2018 - 06:20:00

Identifiants

  • HAL Id : inria-00099744, version 1

Collections

Citation

Richard P. Brent, Samuli Larvala, Paul Zimmermann. A Fast Algorithm for Testing Reducibility of Trinomials mod 2 and Some New Primitive Trinomials of Degree 3021377. Mathematics of Computation, American Mathematical Society, 2003, 72 (243), pp.1443-1452. 〈inria-00099744〉

Partager

Métriques

Consultations de la notice

156