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