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

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.
Mots-clés :
Document type :
Journal articles
Domain :

https://hal.inria.fr/inria-00099744
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 9:40:51 AM
Last modification on : Friday, October 16, 2020 - 4:02:02 PM

### Identifiers

• HAL Id : inria-00099744, version 1

### 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⟩

Record views