Remote Access Mathematics of Computation
Green Open Access

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

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?)

  • 1. E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968. MR 38:6873
  • 2. I. F. Blake, S. Gao and R. J. Lambert, Constructive problems for irreducible polynomials over finite fields, in Information Theory and Applications, Lecture Notes in Computer Science 793, Springer-Verlag, Berlin, 1994, 1-23. MR 95c:94007
  • 3. I. F. Blake, S. Gao and R. J. Lambert, Construction and distribution problems for irreducible trinomials over finite fields, Applications of Finite Fields, Oxford Univ. Press, New York, 1996, pp. 19-32. MR 98a:11170
  • 4. R. P. Brent, Random number generation and simulation on vector and parallel computers (extended abstract), Proc. Fourth Euro-Par Conference, Lecture Notes in Computer Science 1470, Springer-Verlag, Berlin, 1998, 1-20.
  • 5. R. P. Brent, S. Larvala and P. Zimmermann, A Fast Algorithm for Testing Irreducibility of Trinomials mod 2 (preliminary report), Report PRG-TR-13-00, Oxford University Computing Laboratory, 30 December 2000. See
  • 6. J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. S. Wagstaff, Jr., Factorizations of $b^n \pm 1$, $b = 2, 3, 5, 6, 7, 10, 11, 12$up to high powers, 2nd ed., Amer. Math. Soc., Providence, RI, 1988. Updates available from MR 90d:11009
  • 7. H. Fredricksen and R. Wisniewski, ``On trinomials $x^n + x^2 + 1$ and $x^{8l\pm 3} + x^k + 1$ irreducible over $\operatorname{GF}(2)$'', Inform. and Control 50 (1981), 58-63. MR 84i:12013
  • 8. GIMPS, The Great Internet Mersenne Prime Search,
  • 9. S. W. Golomb, Shift register sequences, Holden-Day, San Francisco, 1967. MR 39:3906 Revised edition, Aegean Park Press, 1982, ISBN 0-89412-048-4
  • 10. J. R. Heringa, H. W. J. Blöte and A. Compagner. New primitive trinomials of Mersenne-exponent degrees for random-number generation, International J. of Modern Physics C 3 (1992), 561-564. MR 94a:11118
  • 11. Intel Corporation, MMX Technology Programmer's Reference Manual. Available from
  • 12. T. Kumada, H. Leeb, Y. Kurita and M. Matsumoto, New primitive $t$-nomials $(t = 3$, $5)$ over $\operatorname{GF}(2)$whose degree is a Mersenne exponent, Math. Comp. 69 (2000), 811-814. MR 2000i:11183
  • 13. T. Kumada, Y. Kurita and M. Matsumoto, Corrigenda to ``New primitive $t$-nomials $(t = 3$, $5)$ over $\operatorname{GF}(2)$whose degree is a Mersenne exponent, and some new primitive pentanomials'', Math. Comp. 71 (2002), 1337-1338.
  • 14. Y. Kurita and M. Matsumoto, Primitive $t$-nomials $(t = 3, 5)$ over GF$(2)$whose degree is a Mersenne exponent $\le 44497$, Math. Comp.56 (1991), 817-821. MR 91h:11138
  • 15. H. W. Lenstra and R. J. Schoof, Primitive normal bases for finite fields, Math. Comp.48 (1987), 217-231. MR 88c:11076
  • 16. R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications, Cambridge Univ. Press, Cambridge, second edition, 1994. MR 95f:11098
  • 17. M. Matsumoto, Private communication by email, 17 July 2000.
  • 18. A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, New York, 1997. . MR 99g:94015
  • 19. O. Ore, ``Contributions to the theory of finite fields'', Trans. Amer. Math. Soc. 36 (1934), 243-274.
  • 20. E. R. Rodemich and H. Rumsey, Jr., Primitive trinomials of high degree, Math. Comp.22 (1968), 863-865. MR 39:177
  • 21. W. Stahnke, Primitive binary polynomials, Math. Comp.27 (1973), 977-980. MR 48:6064
  • 22. R. G. Swan, Factorization of polynomials over finite fields, Pacific J. Math.12 (1962), 1099-1106. MR 26:2432
  • 23. S. Tatham and J. Hall, NASM v0.98, the Netwide Assembler, available from .
  • 24. E. J. Watson, Primitive polynomials (mod 2), Math. Comp.16 (1962), 368-369. MR 26:5764
  • 25. N. Zierler, ``On the theorem of Gleason and Marsh'', Proc. Amer. Math. Soc. 9 (1958), 236-237. MR 20:851
  • 26. N. Zierler, Primitive trinomials whose degree is a Mersenne exponent, Inform. and Control15 (1969), 67-69. MR 39:5522
  • 27. N. Zierler, On $x^n + x + 1$ over $\operatorname{GF}(2)$, Inform. and Control 16 (1970), 502-505. MR 42:5955

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

Samuli Larvala
Affiliation: Helsinki University of Technology, Espoo, Finland

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

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

American Mathematical Society