Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

A fast algorithm for testing reducibility of trinomials mod 2 and some new primitive trinomials of degree 3021377


Authors: Richard P. Brent, Samuli Larvala and Paul Zimmermann
Journal: Math. Comp. 72 (2003), 1443-1452
MSC (2000): Primary 11B83, 11Y16; Secondary 11-04, 11K35, 11N35, 11R09, 11T06, 11Y55, 12-04, 65Y10, 68Q25
Published electronically: December 18, 2002
MathSciNet review: 1972745
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The standard algorithm for testing reducibility of a trinomial of prime degree $r$ over $\operatorname{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 et al. The two results for $r = 3021377$ are primitive trinomials of the highest known degree.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11B83, 11Y16, 11-04, 11K35, 11N35, 11R09, 11T06, 11Y55, 12-04, 65Y10, 68Q25

Retrieve articles in all journals with MSC (2000): 11B83, 11Y16, 11-04, 11K35, 11N35, 11R09, 11T06, 11Y55, 12-04, 65Y10, 68Q25


Additional Information

Richard P. Brent
Affiliation: Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford, OX1 3QD, England
Email: Richard.Brent@comlab.ox.ac.uk

Samuli Larvala
Affiliation: Helsinki University of Technology, Espoo, Finland
Email: slarvala@cc.hut.fi

Paul Zimmermann
Affiliation: LORIA/INRIA Lorraine, 615 rue du jardin botanique, BP 101, F-54602 Villers-lès-Nancy, France
Email: Paul.Zimmermann@loria.fr

DOI: http://dx.doi.org/10.1090/S0025-5718-02-01478-3
PII: S 0025-5718(02)01478-3
Keywords: Irreducible polynomials, irreducible trinomials, primitive polynomials, primitive trinomials, Mersenne exponents, Mersenne numbers, random number generators
Received by editor(s): July 9, 2001
Published electronically: December 18, 2002
Article copyright: © Copyright 2002 American Mathematical Society