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

Brent, Richard; Larvala, Samuli; Zimmermann, Paul

doi:10.1090/S0025-5718-02-01478-3

A fast algorithm for testing reducibility of trinomials mod 2 and some new primitive trinomials of degree 3021377
HTML articles powered by AMS MathViewer

by Richard P. Brent, Samuli Larvala and Paul Zimmermann PDF

Math. Comp. 72 (2003), 1443-1452 Request permission

Abstract:

The standard algorithm for testing reducibility of a trinomial of prime degree $r$ over $\mathrm {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

Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR 0238597
Ian F. Blake, Shuhong Gao, and Robert Lambert, Constructive problems for irreducible polynomials over finite fields, Information theory and applications (Rockland, ON, 1993) Lecture Notes in Comput. Sci., vol. 793, Springer, Berlin, 1994, pp. 1–23. MR 1289223, DOI 10.1007/3-540-57936-2_{2}7
Ian F. Blake, Shuhong Gao, and Robert J. Lambert, Construction and distribution problems for irreducible trinomials over finite fields, Applications of finite fields (Egham, 1994) Inst. Math. Appl. Conf. Ser. New Ser., vol. 59, Oxford Univ. Press, New York, 1996, pp. 19–32. MR 1444823
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
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
John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^n \pm 1$, 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. $b=2,3,5,6,7,10,11,12$ up to high powers. MR 996414, DOI 10.1090/conm/022
H. Fredricksen and R. Wisniewski, On trinomials $x^{n}+x^{2}+1$ and $x^{8l\pm 3}+x^{k}+1$ irreducible over $\textrm {GF}(2)$, Inform. and Control 50 (1981), no. 1, 58–63. MR 665139, DOI 10.1016/S0019-9958(81)90144-3
GIMPS, The Great Internet Mersenne Prime Search, http://www.mersenne.org/
L. C. Young, On an inequality of Marcel Riesz, Ann. of Math. (2) 40 (1939), 567–574. MR 39, DOI 10.2307/1968941
J. R. Heringa, H. W. J. Blöte, and A. Compagner, New primitive trinomials of Mersenne-exponent degrees for random-number generation, Internat. J. Modern Phys. C 3 (1992), no. 3, 561–564. MR 1169571, DOI 10.1142/S0129183192000361
Intel Corporation, MMX Technology Programmer’s Reference Manual. Available from http://developer.intel.com.
Toshihiro Kumada, Hannes Leeb, Yoshiharu Kurita, and Makoto Matsumoto, New primitive $t$-nomials $(t=3,5)$ over $\rm GF(2)$ whose degree is a Mersenne exponent, Math. Comp. 69 (2000), no. 230, 811–814. MR 1665959, DOI 10.1090/S0025-5718-99-01168-0
T. Kumada, Y. Kurita and M. Matsumoto, Corrigenda to “New primitive $t$-nomials $(t = 3$, $5)$ over $\mathrm {GF}(2)$ whose degree is a Mersenne exponent, and some new primitive pentanomials”, Math. Comp. 71 (2002), 1337–1338.
Yoshiharu Kurita and Makoto Matsumoto, Primitive $t$-nomials $(t=3,5)$ over $\textrm {GF}(2)$ whose degree is a Mersenne exponent $\le 44497$, Math. Comp. 56 (1991), no. 194, 817–821. MR 1068813, DOI 10.1090/S0025-5718-1991-1068813-6
H. W. Lenstra Jr. and R. J. Schoof, Primitive normal bases for finite fields, Math. Comp. 48 (1987), no. 177, 217–231. MR 866111, DOI 10.1090/S0025-5718-1987-0866111-3
Rudolf Lidl and Harald Niederreiter, Introduction to finite fields and their applications, 1st ed., Cambridge University Press, Cambridge, 1994. MR 1294139, DOI 10.1017/CBO9781139172769
M. Matsumoto, Private communication by email, 17 July 2000.
Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of applied cryptography, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1997. With a foreword by Ronald L. Rivest. MR 1412797
O. Ore, “Contributions to the theory of finite fields”, Trans. Amer. Math. Soc. 36 (1934), 243–274.
Eugene R. Rodemich and Howard Rumsey Jr., Primitive trinomials of high degree, Math. Comp. 22 (1968), 863–865. MR 238813, DOI 10.1090/S0025-5718-1968-0238813-1
Wayne Stahnke, Primitive binary polynomials, Math. Comp. 27 (1973), 977–980. MR 327722, DOI 10.1090/S0025-5718-1973-0327722-7
Richard G. Swan, Factorization of polynomials over finite fields, Pacific J. Math. 12 (1962), 1099–1106. MR 144891
S. Tatham and J. Hall, NASM v0.98, the Netwide Assembler, available from http://www.web-sites.co.uk/nasm/docs/.
E. J. Watson, Primitive polynomials $(\textrm {mod}\ 2)$, Math. Comp. 16 (1962), 368–369. MR 148256, DOI 10.1090/S0025-5718-1962-0148256-1
Neal Zierler, On the theorem of Gleason and Marsh, Proc. Amer. Math. Soc. 9 (1958), 236–237. MR 94332, DOI 10.1090/S0002-9939-1958-0094332-2
Neal Zierler, Primitive trinomials whose degree is a Mersenne exponent, Information and Control 15 (1969), 67–69. MR 244205
Neal Zierler, On $x^{n}+x+1$ over $\textrm {GF}(2)$, Information and Control 16 (1970), 502–505. MR 271072