Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On the existence and non-existence of elliptic pseudoprimes

Author: Siguna Müller
Journal: Math. Comp. 79 (2010), 1171-1190
MSC (2000): Primary 11Y11; Secondary 11Y40, 11A51
Published electronically: October 16, 2009
MathSciNet review: 2600561
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In a series of papers, D. Gordon and C. Pomerance demonstrated that pseudoprimes on elliptic curves behave in many ways very similar to pseudoprimes related to Lucas sequences. In this paper we give an answer to a challenge that was posted by D. Gordon in 1989. The challenge was to either prove that a certain composite $ N \equiv 1 \bmod 4$ did not exist, or to explicitly calculate such a number. In this paper, we both present such a specific composite (for Gordon's curve with CM by $ \mathbb{Q}(\sqrt{-7})$), as well as a proof of the non-existence (for curves with CM by $ \mathbb{Q}(\sqrt{-3}$)). We derive some criteria for the group structure of CM curves that allow testing for all composites, including $ N \equiv 3 \bmod 4$ which had been excluded by Gordon. This gives rise to another type of examples of composites where strong elliptic pseudoprimes are not Euler elliptic pseudoprimes.

References [Enhancements On Off] (What's this?)

  • 1. W. R. Alford, Andrew Granville, and Carl Pomerance, There are infinitely many Carmichael numbers, Annals of Mathematics 139 (1994), 703-722, URL: entries.html#1994/alford.
  • 2. Daniel Bleichenbacher, Efficiency and security of cryptosystems based on number theory, Ph.D. thesis, 1996, URL:
  • 3. Richard Crandall and Carl Pomerance, Prime numbers, A computational perspective. Springer-Verlag, New York, 2001.MR 2002a:11007
  • 4. Daniel M. Gordon, On the number of elliptic pseudoprimes, Math. Comp. 52 (1989), no. 185, 231-245. MR 946604 (89f:11169)
  • 5. -, Pseudoprimes on elliptic curves, Théorie des nombres (Quebec, PQ, 1987), de Gruyter, Berlin, 1989, pp. 290-305. MR 1024570 (91g:11158)
  • 6. Daniel M. Gordon and Carl Pomerance, The distribution of Lucas and elliptic pseudoprimes, Math. Comp. 57 (1991), no. 196, 825-838. MR 1094951 (92h:11081)
  • 7. Jon Grantham, A probable prime test with high confidence, Journal of Number Theory 72 (1998), 32-47, URL: 1643284 (2000e:11160)
  • 8. -, Frobenius pseudoprimes, Mathematics of Computation 70 (2001), 873-891, URL: 1680879 (2001g:11191)
  • 9. Anthony W. Knapp, Elliptic curves, Mathematical Notes, vol. 40, Princeton University Press, Princeton, NJ, 1992. MR 1193029 (93j:11032)
  • 10. Neal Koblitz, Introduction to elliptic curves and modular forms, second ed., Graduate Texts in Mathematics, vol. 97, Springer-Verlag, New York, 1993. MR 1216136 (94a:11078)
  • 11. Siguna Müller, On QF-pseudoprimes and second-order recurrence sequences, Contributions to general algebra, 12 (Vienna, 1999), Heyn, Klagenfurt, 2000, pp. 299-310. MR 1777670 (2001e:11016)
  • 12. René Schoof, Elliptic curves over finite fields and the computation of square roots mod $ p$, Math. Comp. 44 (1985), no. 170, 483-494. MR 777280 (86e:11122)
  • 13. -, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 219-254, Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). MR 1413578 (97i:11070)
  • 14. Lawrence C. Washington, Elliptic curves: Number theory and cryptography, Discrete Mathematics and Its Applications, Chapman & Hall/CRC, May 2003.
  • 15. H. C. Williams and C. R. Zarnke, Some algorithms for solving a cubic congruence modulo $ p$, Utilitas Math. 6 (1974), 285-306. MR 0389730 (52 #10561)
  • 16. Hugh C. Williams, Édouard Lucas and primality testing, John Wiley & Sons Inc., New York, 1998, A Wiley-Interscience Publication. MR 2000b:11139

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y11, 11Y40, 11A51

Retrieve articles in all journals with MSC (2000): 11Y11, 11Y40, 11A51

Additional Information

Siguna Müller
Affiliation: Department of Mathematics, RH 311, University of Wyoming, Laramie, Wyoming 82071

Received by editor(s): August 28, 2008
Received by editor(s) in revised form: December 4, 2008, and March 4, 2009
Published electronically: October 16, 2009
Article copyright: © Copyright 2009 American Mathematical Society

American Mathematical Society