Advertisement

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 

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Atkin, A.O.L., Morain, F.: Elliptic Curves and Primality Proving. Mathematics of Computation 61, 29–68 (1993)zbMATHCrossRefMathSciNetGoogle Scholar
  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)zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    Gross, B.H.: An Elliptic Curve Test for Mersenne Primes. Journal of Number Theory 110, 114–119 (2005)zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    Koblitz, N.: Elliptic Curve Cryptography. Mathematics of Computation 48, 203–209 (1987)zbMATHCrossRefMathSciNetGoogle Scholar
  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)zbMATHCrossRefGoogle Scholar
  7. 7.
    Lenstra Jr., H.W.: Factoring Integers with Elliptic Curves. Annals of Mathematics 126, 649–673 (1987)CrossRefMathSciNetGoogle Scholar
  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)zbMATHCrossRefGoogle Scholar
  12. 12.
    Silverman, J.H.: The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics, vol. 106. Springer, Heidelberg (1994)zbMATHGoogle Scholar
  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)zbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Song Y. Yan
    • 1
  • Glyn James
    • 1
  1. 1.Faculty of Engineering & ComputingCoventry UniversityCoventryUK

Personalised recommendations