Abstract
The current primality test in use for Mersenne primes continues to be the Lucas-Lehmer test, invented by Lucas in 1876 and proved by Lehmer in 1935. In this paper, a practical approach to an elliptic curve test of Gross for Mersenne primes, is discussed and analyzed. The most important advantage of the test is that, unlike the Lucas-Lehmer test which requires \({\cal O}(p)\) arithmetic operations and \({\cal O}(p^3)\) bit operations in order to determine whether or not M p =2p–1 is prime, it only needs \({\cal O}(\lambda)\) arithmetic operations and \({\cal O}(\lambda^3)\) bit operations, with λ≪p. Hence it is more efficient than the Lucas-Lehmer test, but is still as simple, elegant and practical.
The authors would like to thank Prof Benedict Gross of the Department of Mathematics at Harvard University for his advice to work on the computational aspects of the elliptic curve test for Mersenne primes. This paper was written while the first author visited the Dept of Computer Science at the University of Toronto hosted by Prof Stephen Cook and supported by the Royal Society London.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
We’re sorry, something doesn't seem to be working properly.
Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.
References
Atkin, A.O.L., Morain, F.: Elliptic Curves and Primality Proving. Mathematics of Computation 61, 29–68 (1993)
Brent, R.P., Cohen, G.L., te Riele, H.J.J.: Improved Techniques for Lower Bounds for Odd Perfect Numbers. Mathematics of Computation 57, 857–868 (1991)
Gross, B.H.: An Elliptic Curve Test for Mersenne Primes. Journal of Number Theory 110, 114–119 (2005)
Koblitz, N.: Elliptic Curve Cryptography. Mathematics of Computation 48, 203–209 (1987)
Lang, S.: Fundamentals of Dionphtine Geometry. Springer, Heidelberg (1983)
Lehmer, D.H.: On Lucas’s Test for the Primality of Mersenne’s Numbers. Journal of London Mathematical Society 10, 162–165 (1935)
Lenstra Jr., H.W.: Factoring Integers with Elliptic Curves. Annals of Mathematics 126, 649–673 (1987)
Lucas, E.: Noveaux Théorèmes d’Arithmétique Supèrieure. C. R. Acad. Sci. Paris 83, 1286–1288 (1876)
Miller, V.: Uses of Elliptic Curves in Cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
Morain, F.: Implementing the Asymptotically Fast Version of the Elliptic Curve Primality Proving Algorithm (October 21, 2005), See: http://www.lix.polytechnique.fr/~morain/Articles/fastecpp-final.pdf
Rosen, M.: A Proof of the Lucase-Lehmer Test. American Mathematics Monthly 95, 855–856 (1988)
Silverman, J.H.: The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics, vol. 106. Springer, Heidelberg (1994)
Wiles, A.: Modular Elliptic Curves and Fermat’s Last Theorem. Annals of Mathematics 141, 443–551 (1995)
Yan, S.Y.: Number Theory for Computing, 2nd edn. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yan, S.Y., James, G. (2006). Testing Mersenne Primes with Elliptic Curves. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds) Computer Algebra in Scientific Computing. CASC 2006. Lecture Notes in Computer Science, vol 4194. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11870814_27
Download citation
DOI: https://doi.org/10.1007/11870814_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-45182-2
Online ISBN: 978-3-540-45195-2
eBook Packages: Computer ScienceComputer Science (R0)