On the number of elliptic pseudoprimes

Author:
Daniel M. Gordon

Journal:
Math. Comp. **52** (1989), 231-245

MSC:
Primary 11Y11; Secondary 11G05

DOI:
https://doi.org/10.1090/S0025-5718-1989-0946604-2

MathSciNet review:
946604

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For an elliptic curve *E* with complex multiplication by an order in , a point *P* of infinite order on *E*, and any prime *p* with , we have that , where *O* is the point at infinity and calculations are done using the addition law for *E*. Any composite number which satisfies these conditions is called an elliptic pseudoprime. In this paper it is shown that, assuming the Generalized Riemann Hypothesis, elliptic pseudoprimes are less numerous than primes. In particular, on the GRH, the number of elliptic pseudoprimes less than *x* is . For certain curves it is shown that infinitely many elliptic pseudoprimes exist.

**[1]**William Adams and Daniel Shanks,*Strong primality tests that are not sufficient*, Math. Comp.**39**(1982), no. 159, 255–300. MR**658231**, https://doi.org/10.1090/S0025-5718-1982-0658231-9**[2]**Robert Baillie and Samuel S. Wagstaff Jr.,*Lucas pseudoprimes*, Math. Comp.**35**(1980), no. 152, 1391–1417. MR**583518**, https://doi.org/10.1090/S0025-5718-1980-0583518-6**[3]**W. Bosma,*Primality Testing Using Elliptic Curves*, Report 85-12, Mathematisch Instituut, Universiteit van Amsterdam, 1985.**[4]**K. Chandrasekharan,*Elliptic functions*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 281, Springer-Verlag, Berlin, 1985. MR**808396****[5]**D. V. Chudnovsky and G. V. Chudnovsky,*Sequences of numbers generated by addition in formal groups and new primality and factorization tests*, Adv. in Appl. Math.**7**(1986), no. 4, 385–434. MR**866702**, https://doi.org/10.1016/0196-8858(86)90023-0**[6]**P. Erdös,*On pseudoprimes and Carmichael numbers*, Publ. Math. Debrecen**4**(1956), 201–206. MR**0079031****[7]**S. Goldwasser & J. Kilian,*Almost All Primes Can be Quickly Certified*, Proc. 18th Annual ACM Sympos. on Theory of Computing, 1986, pp. 316-329.**[8]**Daniel M. Gordon,*Pseudoprimes on elliptic curves*, Théorie des nombres (Quebec, PQ, 1987) de Gruyter, Berlin, 1989, pp. 290–305. MR**1024570****[9]**Rajiv Gupta and M. Ram Murty,*Primitive points on elliptic curves*, Compositio Math.**58**(1986), no. 1, 13–44. MR**834046****[10]**Kenneth F. Ireland and Michael I. Rosen,*A classical introduction to modern number theory*, Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York-Berlin, 1982. Revised edition of Elements of number theory. MR**661047****[11]**Péter Kiss, Bui Minh Phong, and Erik Lieuwens,*On Lucas pseudoprimes which are products of 𝑠 primes*, Fibonacci numbers and their applications (Patras, 1984) Math. Appl., vol. 28, Reidel, Dordrecht, 1986, pp. 131–139. MR**857820****[12]**Donald E. Knuth,*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**633878****[13]**G. C. Kurtz, Daniel Shanks, and H. C. Williams,*Fast primality tests for numbers less than 50⋅10⁹*, Math. Comp.**46**(1986), no. 174, 691–701. MR**829639**, https://doi.org/10.1090/S0025-5718-1986-0829639-7**[14]**J. C. Lagarias and A. M. Odlyzko,*Effective versions of the Chebotarev density theorem*, Algebraic number fields: 𝐿-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR**0447191****[15]**H. W. Lenstra Jr.,*Factoring integers with elliptic curves*, Ann. of Math. (2)**126**(1987), no. 3, 649–673. MR**916721**, https://doi.org/10.2307/1971363**[16]**H. W. Lenstra, Jr., "Elliptic curves and number theoretic algorithms," preprint, 1986.**[17]**Peter L. Montgomery,*Speeding the Pollard and elliptic curve methods of factorization*, Math. Comp.**48**(1987), no. 177, 243–264. MR**866113**, https://doi.org/10.1090/S0025-5718-1987-0866113-7**[18]**Carl Pomerance,*On the distribution of pseudoprimes*, Math. Comp.**37**(1981), no. 156, 587–593. MR**628717**, https://doi.org/10.1090/S0025-5718-1981-0628717-0**[19]**Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr.,*The pseudoprimes to 25⋅10⁹*, Math. Comp.**35**(1980), no. 151, 1003–1026. MR**572872**, https://doi.org/10.1090/S0025-5718-1980-0572872-7**[20]**Michael O. Rabin,*Probabilistic algorithm for testing primality*, J. Number Theory**12**(1980), no. 1, 128–138. MR**566880**, https://doi.org/10.1016/0022-314X(80)90084-0**[21]**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**[22]**Joseph H. Silverman,*The arithmetic of elliptic curves*, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR**817210****[23]**H. M. Stark,*A complete determination of the complex quadratic fields of class-number one*, Michigan Math. J.**14**(1967), 1–27. MR**0222050****[24]**Morgan Ward,*Memoir on elliptic divisibility sequences*, Amer. J. Math.**70**(1948), 31–74. MR**0023275**, https://doi.org/10.2307/2371930**[25]**Morgan Ward,*The intrinsic divisors of Lehmer numbers*, Ann. of Math. (2)**62**(1955), 230–236. MR**0071446**, https://doi.org/10.2307/1969677**[26]**Morgan Ward,*The law of repetition of primes in an elliptic divisibility sequence*, Duke Math. J.**15**(1948), 941–946. MR**0027286****[27]**Don Zagier,*Large integral points on elliptic curves*, Math. Comp.**48**(1987), no. 177, 425–436. MR**866125**, https://doi.org/10.1090/S0025-5718-1987-0866125-3

Retrieve articles in *Mathematics of Computation*
with MSC:
11Y11,
11G05

Retrieve articles in all journals with MSC: 11Y11, 11G05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1989-0946604-2

Article copyright:
© Copyright 1989
American Mathematical Society