Mathematics of Computation

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

Author(s): Richard P. Brent; Samuli Larvala; 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
Posted: December 18, 2002
Retrieve article in: PDF DVI PostScript

Abstract: The standard algorithm for testing reducibility of a trinomial of prime degree

over $\operatorname{GF}(2)$ requires

bits of memory. We describe a new algorithm which requires only

bits of memory and significantly fewer memory references and bit-operations than the standard algorithm.

is a Mersenne prime, then an irreducible trinomial of degree

is necessarily primitive. We give primitive trinomials for the Mersenne exponents

, and

. The results for

extend and correct some computations of Kumada et al. The two results for

are primitive trinomials of the highest known degree.

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. http://www.comlab.ox.ac.uk/oucl/work/richard.brent/pub/pub185.html
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 http://www.comlab.ox.ac.uk/oucl/work/richard.brent/pub/pub199.html
6.: J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. S. Wagstaff, Jr., Factorizations of $b^n \pm 1$ , up to high powers, 2nd ed., Amer. Math. Soc., Providence, RI, 1988. Updates available from http://www.cerias.purdue.edu/homes/ssw/cun/. MR 90d:11009
7.: H. Fredricksen and R. Wisniewski, ``On trinomials 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, http://www.mersenne.org/
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 http://developer.intel.com.
12.: T. Kumada, H. Leeb, Y. Kurita and M. Matsumoto, New primitive -nomials , 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 -nomials , 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 -nomials over GFwhose 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. http://cacr.math.uwaterloo.ca/hac/ . 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 http://www.web-sites.co.uk/nasm/docs/ .
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 over $\operatorname{GF}(2)$ , Inform. and Control 16 (1970), 502-505. MR 42:5955

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: 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
Posted: December 18, 2002
Copyright of article: Copyright 2002, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS