On the existence and non-existence of elliptic pseudoprimes
HTML articles powered by AMS MathViewer
- by Siguna Müller PDF
- Math. Comp. 79 (2010), 1171-1190 Request permission
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
- W. R. Alford, Andrew Granville, and Carl Pomerance, There are infinitely many Carmichael numbers, Annals of Mathematics 139 (1994), 703–722, URL: http://cr.yp.to/bib/entries.html#1994/alford.
- Daniel Bleichenbacher, Efficiency and security of cryptosystems based on number theory, Ph.D. thesis, 1996, URL: http://www.bell-labs.com/user/bleichen/diss/thesis.html.
- M. Gontcharoff, Sur quelques séries d’interpolation généralisant celles de Newton et de Stirling, Uchenye Zapiski Moskov. Gos. Univ. Matematika 30 (1939), 17–48 (Russian, with French summary). MR 0002002
- Daniel M. Gordon, On the number of elliptic pseudoprimes, Math. Comp. 52 (1989), no. 185, 231–245. MR 946604, DOI 10.1090/S0025-5718-1989-0946604-2
- Daniel M. Gordon, Pseudoprimes on elliptic curves, Théorie des nombres (Quebec, PQ, 1987) de Gruyter, Berlin, 1989, pp. 290–305. MR 1024570
- Daniel M. Gordon and Carl Pomerance, The distribution of Lucas and elliptic pseudoprimes, Math. Comp. 57 (1991), no. 196, 825–838. MR 1094951, DOI 10.1090/S0025-5718-1991-1094951-8
- Jon Grantham, A probable prime test with high confidence, J. Number Theory 72 (1998), no. 1, 32–47. MR 1643284, DOI 10.1006/jnth.1998.2247
- Jon Grantham, Frobenius pseudoprimes, Math. Comp. 70 (2001), no. 234, 873–891. MR 1680879, DOI 10.1090/S0025-5718-00-01197-2
- Anthony W. Knapp, Elliptic curves, Mathematical Notes, vol. 40, Princeton University Press, Princeton, NJ, 1992. MR 1193029
- Neal Koblitz, Introduction to elliptic curves and modular forms, 2nd ed., Graduate Texts in Mathematics, vol. 97, Springer-Verlag, New York, 1993. MR 1216136, DOI 10.1007/978-1-4612-0909-6
- 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
- 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, DOI 10.1090/S0025-5718-1985-0777280-6
- René Schoof, 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
- Lawrence C. Washington, Elliptic curves: Number theory and cryptography, Discrete Mathematics and Its Applications, Chapman & Hall/CRC, May 2003.
- H. C. Williams and C. R. Zarnke, Some algorithms for solving a cubic congruence modulo $p$, Utilitas Math. 6 (1974), 285–306. MR 389730
- P. Erdös, On the distribution of normal point groups, Proc. Nat. Acad. Sci. U.S.A. 26 (1940), 294–297. MR 2000, DOI 10.1073/pnas.26.4.294
Additional Information
- Siguna Müller
- Affiliation: Department of Mathematics, RH 311, University of Wyoming, Laramie, Wyoming 82071
- Email: smuller@uwyo.edu
- 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
- © Copyright 2009 American Mathematical Society
- Journal: Math. Comp. 79 (2010), 1171-1190
- MSC (2000): Primary 11Y11; Secondary 11Y40, 11A51
- DOI: https://doi.org/10.1090/S0025-5718-09-02275-3
- MathSciNet review: 2600561