# Testing Mersenne Primes with Elliptic Curves

• Song Y. Yan
• Glyn James
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4194)

## 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 =2 p –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.

## Keywords

Mersenne numbers Mersenne primes Lucas-Lehmer test elliptic curve test

## References

1. 1.
Atkin, A.O.L., Morain, F.: Elliptic Curves and Primality Proving. Mathematics of Computation 61, 29–68 (1993)
2. 2.
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)
3. 3.
Gross, B.H.: An Elliptic Curve Test for Mersenne Primes. Journal of Number Theory 110, 114–119 (2005)
4. 4.
Koblitz, N.: Elliptic Curve Cryptography. Mathematics of Computation 48, 203–209 (1987)
5. 5.
Lang, S.: Fundamentals of Dionphtine Geometry. Springer, Heidelberg (1983)Google Scholar
6. 6.
Lehmer, D.H.: On Lucas’s Test for the Primality of Mersenne’s Numbers. Journal of London Mathematical Society 10, 162–165 (1935)
7. 7.
Lenstra Jr., H.W.: Factoring Integers with Elliptic Curves. Annals of Mathematics 126, 649–673 (1987)
8. 8.
Lucas, E.: Noveaux Théorèmes d’Arithmétique Supèrieure. C. R. Acad. Sci. Paris 83, 1286–1288 (1876)Google Scholar
9. 9.
Miller, V.: Uses of Elliptic Curves in Cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)Google Scholar
10. 10.
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
11. 11.
Rosen, M.: A Proof of the Lucase-Lehmer Test. American Mathematics Monthly 95, 855–856 (1988)
12. 12.
Silverman, J.H.: The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics, vol. 106. Springer, Heidelberg (1994)
13. 13.
Wiles, A.: Modular Elliptic Curves and Fermat’s Last Theorem. Annals of Mathematics 141, 443–551 (1995)Google Scholar
14. 14.
Yan, S.Y.: Number Theory for Computing, 2nd edn. Springer, Heidelberg (2002)