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

DOI:
https://doi.org/10.1090/S0025-5718-09-02275-3

Published electronically:
October 16, 2009

MathSciNet review:
2600561

Full-text PDF

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 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 ), as well as a proof of the non-existence (for curves with CM by )). We derive some criteria for the group structure of CM curves that allow testing for all composites, including 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.

**1.**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`.**2.**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`.**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**, https://doi.org/10.1090/S0025-5718-1989-0946604-2**5.**Daniel M. Gordon,*Pseudoprimes on elliptic curves*, Théorie des nombres (Quebec, PQ, 1987) de Gruyter, Berlin, 1989, pp. 290–305. MR**1024570****6.**Daniel M. Gordon and Carl Pomerance,*The distribution of Lucas and elliptic pseudoprimes*, Math. Comp.**57**(1991), no. 196, 825–838. MR**1094951**, https://doi.org/10.1090/S0025-5718-1991-1094951-8**7.**Jon Grantham,*A probable prime test with high confidence*, J. Number Theory**72**(1998), no. 1, 32–47. MR**1643284**, https://doi.org/10.1006/jnth.1998.2247**8.**Jon Grantham,*Frobenius pseudoprimes*, Math. Comp.**70**(2001), no. 234, 873–891. MR**1680879**, https://doi.org/10.1090/S0025-5718-00-01197-2**9.**Anthony W. Knapp,*Elliptic curves*, Mathematical Notes, vol. 40, Princeton University Press, Princeton, NJ, 1992. MR**1193029****10.**Neal Koblitz,*Introduction to elliptic curves and modular forms*, 2nd ed., Graduate Texts in Mathematics, vol. 97, Springer-Verlag, New York, 1993. MR**1216136****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****12.**René Schoof,*Elliptic curves over finite fields and the computation of square roots mod 𝑝*, Math. Comp.**44**(1985), no. 170, 483–494. MR**777280**, https://doi.org/10.1090/S0025-5718-1985-0777280-6**13.**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****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 𝑝*, Utilitas Math.**6**(1974), 285–306. MR**0389730****16.**Hugh C. Williams,*Édouard Lucas and primality testing*, John Wiley & Sons Inc., New York, 1998, A Wiley-Interscience Publication. MR**2000b:11139**

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

Email:
smuller@uwyo.edu

DOI:
https://doi.org/10.1090/S0025-5718-09-02275-3

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