Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

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 $ K = {\mathbf{Q}}(\sqrt { - d} )$, a point P of infinite order on E, and any prime p with $ ( - d\vert p) = - 1$, we have that $ (p + 1) \cdot P = O\pmod p$, 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 $ O(x\log \log x/{\log ^2}x)$. For certain curves it is shown that infinitely many elliptic pseudoprimes exist.


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

  • [1] W. W. Adams & D. Shanks, "Strong primality tests that are not sufficient," Math. Comp., v. 39, 1982, pp. 255-300. MR 658231 (84c:10007)
  • [2] R. Baillie & S. S. Wagstaff, Jr., "Lucas pseudoprimes," Math. Comp., v. 35, 1980, pp. 1391-1417. MR 583518 (81j:10005)
  • [3] W. Bosma, Primality Testing Using Elliptic Curves, Report 85-12, Mathematisch Instituut, Universiteit van Amsterdam, 1985.
  • [4] K. Chandrasekharan, Elliptic Functions, Springer-Verlag, New York, 1985. MR 808396 (87e:11058)
  • [5] D. V. Chudnovsky & G. V. Chudnovsky, "Sequences of numbers generated by addition in formal groups and new primality and factorization tests," Adv. in Appl. Math., v. 7, 1987, pp. 385-434. MR 866702 (88h:11094)
  • [6] P. Erdös, "On pseudoprimes and Carmichael numbers," Publ. Math. Debrecen, v. 4, 1956, pp. 201-206. MR 0079031 (18:18e)
  • [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] D. M. Gordon, Pseudoprimes on Elliptic Curves, Proc. Internat. Number Theory Conference, Laval, 1987. (To appear.) MR 1024570 (91g:11158)
  • [9] R. Gupta & M. Ram Murty, "Primitive points on elliptic curves," Compositio Math., v. 58, 1986, pp. 13-44. MR 834046 (87h:11050)
  • [10] K. Ireland & M. Rosen, A Classical Introduction to Modern Number Theory, Graduate Texts in Math., vol. 84, Springer-Verlag, New York, 1982. MR 661047 (83g:12001)
  • [11] P. Kiss, B. M. Phong & E. Lieuwens, "On Lucas pseudoprimes which are the products of s primes," in Fibonacci Numbers and Their Applications, Reidel, Dordrecht, 1986, pp. 131-139. MR 857820 (87j:11017)
  • [12] D. E. Knuth, The Art of Computer Programming, Vol. 2, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [13] G. Kurtz, D. Shanks & H. C. Williams, "Fast primality tests for numbers less than $ 50 \cdot {10^9}$," Math. Comp., v. 46, 1986, pp. 691-701. MR 829639 (87d:11101)
  • [14] J. C. Lagarias & A. M. Odlyzko, "Effective versions of the Chebotarev Density Theorem," Algebraic Number Fields (A. Frölich, ed.), Academic Press, New York, 1977, pp. 409-464. MR 0447191 (56:5506)
  • [15] H. W. Lemstra, Jr., "Factoring integers with elliptic curves," Ann. of Math., v. 126, 1987, pp. 649-673. MR 916721 (89g:11125)
  • [16] H. W. Lenstra, Jr., "Elliptic curves and number theoretic algorithms," preprint, 1986.
  • [17] P. L. Montgomery, "Speeding the Pollard and elliptic curve methods of factorization," Math. Comp., v. 48, 1987, pp. 243-264. MR 866113 (88e:11130)
  • [18] C. Pomerance, "On the distribution of pseudoprimes," Math. Comp., v. 37, 1981, pp. 587-593. MR 628717 (83k:10009)
  • [19] C. Pomerance, J. L. Selfridge & S. S. Wagstaff, Jr., "The pseudoprimes to $ 25\cdot{10^9}$," Math. Comp., v. 35, 1980, pp. 1003-1026. MR 572872 (82g:10030)
  • [20] M. O. Rabin, "Probabilistic algorithm for testing primality," J. Number Theory, v. 12, 1980, pp. 128-138. MR 566880 (81f:10003)
  • [21] R. Schoof, "Elliptic curves over finite fields and the computation of square roots $ \bmod p$," Math. Comp., v. 44, 1985, pp. 483-494. MR 777280 (86e:11122)
  • [22] J. H. Silverman, The Arithmetic of Elliptic Curves, Graduate Texts in Math., vol. 106, Springer-Verlag, New York, 1986. MR 817210 (87g:11070)
  • [23] H. M. Stark, "A complete determination of the complex quadratic fields of class-number one," Michigan Math. J., v. 14, 1967, pp. 1-27. MR 0222050 (36:5102)
  • [24] M. Ward, "Memoir on elliptic divisibility sequences," Amer. J. Math., v. 70, 1948, pp. 31-74. MR 0023275 (9:332j)
  • [25] M. Ward, "The intrinsic divisors of Lehmer numbers," Ann. of Math., v. 62, 1955, pp. 230-236. MR 0071446 (17:127i)
  • [26] M. Ward, "The law of repetition of primes in an elliptic divisibility sequence," Duke Math. J., v. 15, 1948, pp. 941-946. MR 0027286 (10:283e)
  • [27] D. Zagier, "Large integral points on elliptic curves," Math. Comp., v. 48, 1987, pp. 425-436. MR 866125 (87k:11062)

Similar Articles

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

American Mathematical Society