On the number of elliptic pseudoprimes
Author:
Daniel M. Gordon
Journal:
Math. Comp. 52 (1989), 231245
MSC:
Primary 11Y11; Secondary 11G05
MathSciNet review:
946604
Fulltext 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
(84c:10007), http://dx.doi.org/10.1090/S00255718198206582319
 [2]
Robert
Baillie and Samuel
S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417. MR 583518
(81j:10005), http://dx.doi.org/10.1090/S00255718198005835186
 [3]
W. Bosma, Primality Testing Using Elliptic Curves, Report 8512, Mathematisch Instituut, Universiteit van Amsterdam, 1985.
 [4]
K.
Chandrasekharan, Elliptic functions, Grundlehren der
Mathematischen Wissenschaften [Fundamental Principles of Mathematical
Sciences], vol. 281, SpringerVerlag, Berlin, 1985. MR 808396
(87e:11058)
 [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
(88h:11094), http://dx.doi.org/10.1016/01968858(86)900230
 [6]
P.
Erdös, On pseudoprimes and Carmichael numbers, Publ.
Math. Debrecen 4 (1956), 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. 316329.
 [8]
Daniel
M. Gordon, Pseudoprimes on elliptic curves, Théorie des
nombres (Quebec, PQ, 1987) de Gruyter, Berlin, 1989,
pp. 290–305. MR 1024570
(91g:11158)
 [9]
Rajiv
Gupta and M.
Ram Murty, Primitive points on elliptic curves, Compositio
Math. 58 (1986), no. 1, 13–44. MR 834046
(87h:11050)
 [10]
Kenneth
F. Ireland and Michael
I. Rosen, A classical introduction to modern number theory,
Graduate Texts in Mathematics, vol. 84, SpringerVerlag, New
YorkBerlin, 1982. Revised edition of Elements of number theory. MR 661047
(83g:12001)
 [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
(87j:11017)
 [12]
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 [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
(87d:11101), http://dx.doi.org/10.1090/S00255718198608296397
 [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
(56 #5506)
 [15]
H.
W. Lenstra Jr., Factoring integers with elliptic curves, Ann.
of Math. (2) 126 (1987), no. 3, 649–673. MR 916721
(89g:11125), http://dx.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
(88e:11130), http://dx.doi.org/10.1090/S00255718198708661137
 [18]
Carl
Pomerance, On the distribution of
pseudoprimes, Math. Comp.
37 (1981), no. 156, 587–593. MR 628717
(83k:10009), http://dx.doi.org/10.1090/S00255718198106287170
 [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
(82g:10030), http://dx.doi.org/10.1090/S00255718198005728727
 [20]
Michael
O. Rabin, Probabilistic algorithm for testing primality, J.
Number Theory 12 (1980), no. 1, 128–138. MR 566880
(81f:10003), http://dx.doi.org/10.1016/0022314X(80)900840
 [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
(86e:11122), http://dx.doi.org/10.1090/S00255718198507772806
 [22]
Joseph
H. Silverman, The arithmetic of elliptic curves, Graduate
Texts in Mathematics, vol. 106, SpringerVerlag, New York, 1986. MR 817210
(87g:11070)
 [23]
H.
M. Stark, A complete determination of the complex quadratic fields
of classnumber one, Michigan Math. J. 14 (1967),
1–27. MR
0222050 (36 #5102)
 [24]
Morgan
Ward, Memoir on elliptic divisibility sequences, Amer. J.
Math. 70 (1948), 31–74. MR 0023275
(9,332j)
 [25]
Morgan
Ward, The intrinsic divisors of Lehmer numbers, Ann. of Math.
(2) 62 (1955), 230–236. MR 0071446
(17,127i)
 [26]
Morgan
Ward, The law of repetition of primes in an elliptic divisibility
sequence, Duke Math. J. 15 (1948), 941–946. MR 0027286
(10,283e)
 [27]
Don
Zagier, Large integral points on elliptic
curves, Math. Comp. 48
(1987), no. 177, 425–436. MR 866125
(87k:11062), http://dx.doi.org/10.1090/S00255718198708661253
 [1]
 W. W. Adams & D. Shanks, "Strong primality tests that are not sufficient," Math. Comp., v. 39, 1982, pp. 255300. MR 658231 (84c:10007)
 [2]
 R. Baillie & S. S. Wagstaff, Jr., "Lucas pseudoprimes," Math. Comp., v. 35, 1980, pp. 13911417. MR 583518 (81j:10005)
 [3]
 W. Bosma, Primality Testing Using Elliptic Curves, Report 8512, Mathematisch Instituut, Universiteit van Amsterdam, 1985.
 [4]
 K. Chandrasekharan, Elliptic Functions, SpringerVerlag, 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. 385434. MR 866702 (88h:11094)
 [6]
 P. Erdös, "On pseudoprimes and Carmichael numbers," Publ. Math. Debrecen, v. 4, 1956, pp. 201206. 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. 316329.
 [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. 1344. MR 834046 (87h:11050)
 [10]
 K. Ireland & M. Rosen, A Classical Introduction to Modern Number Theory, Graduate Texts in Math., vol. 84, SpringerVerlag, 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. 131139. MR 857820 (87j:11017)
 [12]
 D. E. Knuth, The Art of Computer Programming, Vol. 2, 2nd ed., AddisonWesley, Reading, Mass., 1981. MR 633878 (83i:68003)
 [13]
 G. Kurtz, D. Shanks & H. C. Williams, "Fast primality tests for numbers less than ," Math. Comp., v. 46, 1986, pp. 691701. 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. 409464. MR 0447191 (56:5506)
 [15]
 H. W. Lemstra, Jr., "Factoring integers with elliptic curves," Ann. of Math., v. 126, 1987, pp. 649673. 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. 243264. MR 866113 (88e:11130)
 [18]
 C. Pomerance, "On the distribution of pseudoprimes," Math. Comp., v. 37, 1981, pp. 587593. MR 628717 (83k:10009)
 [19]
 C. Pomerance, J. L. Selfridge & S. S. Wagstaff, Jr., "The pseudoprimes to ," Math. Comp., v. 35, 1980, pp. 10031026. MR 572872 (82g:10030)
 [20]
 M. O. Rabin, "Probabilistic algorithm for testing primality," J. Number Theory, v. 12, 1980, pp. 128138. MR 566880 (81f:10003)
 [21]
 R. Schoof, "Elliptic curves over finite fields and the computation of square roots ," Math. Comp., v. 44, 1985, pp. 483494. MR 777280 (86e:11122)
 [22]
 J. H. Silverman, The Arithmetic of Elliptic Curves, Graduate Texts in Math., vol. 106, SpringerVerlag, New York, 1986. MR 817210 (87g:11070)
 [23]
 H. M. Stark, "A complete determination of the complex quadratic fields of classnumber one," Michigan Math. J., v. 14, 1967, pp. 127. MR 0222050 (36:5102)
 [24]
 M. Ward, "Memoir on elliptic divisibility sequences," Amer. J. Math., v. 70, 1948, pp. 3174. MR 0023275 (9:332j)
 [25]
 M. Ward, "The intrinsic divisors of Lehmer numbers," Ann. of Math., v. 62, 1955, pp. 230236. 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. 941946. MR 0027286 (10:283e)
 [27]
 D. Zagier, "Large integral points on elliptic curves," Math. Comp., v. 48, 1987, pp. 425436. 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:
http://dx.doi.org/10.1090/S00255718198909466042
PII:
S 00255718(1989)09466042
Article copyright:
© Copyright 1989
American Mathematical Society
