Gaussian Mersenne and Eisenstein Mersenne primes

Berrizbeitia, Pedro; Iskra, Boris

doi:10.1090/S0025-5718-10-02324-0

Gaussian Mersenne and Eisenstein Mersenne primes
HTML articles powered by AMS MathViewer

by Pedro Berrizbeitia and Boris Iskra PDF

Math. Comp. 79 (2010), 1779-1791 Request permission

Abstract:

The Biquadratic Reciprocity Law is used to produce a deterministic primality test for Gaussian Mersenne norms which is analogous to the Lucas–Lehmer test for Mersenne numbers. It is shown that the proposed test could not have been obtained from the Quadratic Reciprocity Law and Proth’s Theorem. Other properties of Gaussian Mersenne norms that contribute to the search for large primes are given. The Cubic Reciprocity Law is used to produce a primality test for Eisenstein Mersenne norms. The search for primes in both families (Gaussian Mersenne and Eisenstein Mersenne norms) was implemented in 2004 and ended in November 2005, when the largest primes, known at the time in each family, were found.

References

Pedro Berrizbeitia, Deterministic proofs of primality, Gac. R. Soc. Mat. Esp. 4 (2001), no. 2, 447–456 (Spanish). MR 1852299
Pedro Berrizbeitia and T. G. Berry, Cubic reciprocity and generalised Lucas-Lehmer tests for primality of $A\cdot 3^n\pm 1$, Proc. Amer. Math. Soc. 127 (1999), no. 7, 1923–1925. MR 1487359, DOI 10.1090/S0002-9939-99-04786-3
Pedro Berrizbeitia and T. G. Berry, Biquadratic reciprocity and a Lucasian primality test, Math. Comp. 73 (2004), no. 247, 1559–1564. MR 2047101, DOI 10.1090/S0025-5718-03-01575-8
John Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of $2^{m}\pm 1$, Math. Comp. 29 (1975), 620–647. MR 384673, DOI 10.1090/S0025-5718-1975-0384673-1
John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^{n}\pm 1$, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. $b=2,\,3,\,5,\,6,\,7,\,10,\,11,\,12$ up to high powers. MR 715603
C. Caldwell, The Prime Glossary, http://primes.utm.edu/glossary/
Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. MR 1821158, DOI 10.1007/978-1-4684-9316-0
Andreas Guthmann, Effective primality tests for integers of the forms $N=k\cdot 3^n+1$ and $N=k\cdot 2^m3^n+1$, BIT 32 (1992), no. 3, 529–534. MR 1179238, DOI 10.1007/BF02074886
Miriam Hausman and Harold N. Shapiro, Perfect ideals over the Gaussian integers, Comm. Pure Appl. Math. 29 (1976), no. 3, 323–341. MR 424745, DOI 10.1002/cpa.3160290306
Kenneth F. Ireland and Michael I. Rosen, A classical introduction to modern number theory, Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York-Berlin, 1982. Revised edition of Elements of number theory. MR 661047
Emma Lehmer, Criteria for cubic and quartic residuacity, Mathematika 5 (1958), 20–29. MR 95162, DOI 10.1112/S0025579300001303
Wayne L. McDaniel, Perfect Gaussian integers, Acta Arith. 25 (1973/74), 137–144. MR 332708, DOI 10.4064/aa-25-2-137-144
Paulo Ribenboim, The little book of big primes, Springer-Verlag, New York, 1991. MR 1118843, DOI 10.1007/978-1-4757-4330-2
Robert Spira, The complex sum of divisors, Amer. Math. Monthly 68 (1961), 120–124. MR 148594, DOI 10.2307/2312472
Hugh C. Williams, Édouard Lucas and primality testing, Canadian Mathematical Society Series of Monographs and Advanced Texts, vol. 22, John Wiley & Sons, Inc., New York, 1998. A Wiley-Interscience Publication. MR 1632793
Kenneth S. Williams, On Euler’s criterion for cubic nonresidues, Proc. Amer. Math. Soc. 49 (1975), 277–283. MR 366792, DOI 10.1090/S0002-9939-1975-0366792-0