Elliptic pseudoprimes
HTML articles powered by AMS MathViewer
- by I. Miyamoto and M. Ram Murty PDF
- Math. Comp. 53 (1989), 415-430 Request permission
Abstract:
Let E be an elliptic curve over Q with complex multiplication by an order in an imaginary quadratic field. Let ${\psi _n}$ denote the nth division polynomial, and let P be a rational point of E of infinite order. A natural number n is called an elliptic pseudoprime if $n|{\psi _{n + 1}}(P)$ and n is composite. Let $N(x)$ denote the number of elliptic pseudoprimes up to x. We show that $N(x) \ll x{(\log \log x)^{7/2}}/{(\log x)^{3/2}}$. More generally, if ${P_1}, \ldots ,{P_r}$ are r independent rational points of E which have infinite order, and $\Gamma$ is the subgroup generated by them, denote by ${N_\Gamma }(x)$ the number of composite $n \leq x$ satisfying $n|{\psi _{n + 1}}({P_i})$, $1 \leq i \leq r$. For $r \geq 2$, we prove ${N_\Gamma }(x) \ll x\exp ( - c\sqrt {(\log x)(\log \log x))}$ for some positive constant c.References
- J. W. S. Cassels, Arithmetic on an elliptic curve, Proc. Internat. Congr. Mathematicians (Stockholm, 1962) Inst. Mittag-Leffler, Djursholm, 1963, pp. 234–246. MR 0175891 N. G. de Bruijn, "On the number of positive integers $\leq x$ and free of prime factors $> y$," Indag. Math., v. 13, 1951, pp. 50-60.
- P. Erdös, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201–206. MR 79031
- P. Erdös, On the converse of Fermat’s theorem, Amer. Math. Monthly 56 (1949), 623–624. MR 32691, DOI 10.2307/2304732
- Paul Erdős and Carl Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), no. 173, 259–279. MR 815848, DOI 10.1090/S0025-5718-1986-0815848-X
- Daniel M. Gordon, On the number of elliptic pseudoprimes, Math. Comp. 52 (1989), no. 185, 231–245. MR 946604, DOI 10.1090/S0025-5718-1989-0946604-2 D. M. Gordon, Private communication.
- Rajiv Gupta and M. Ram Murty, Primitive points on elliptic curves, Compositio Math. 58 (1986), no. 1, 13–44. MR 834046 H. Halbertstam & H. E. Richert, Sieve Methods, Academic Press, London, 1974.
- Serge Lang, Elliptic functions, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Amsterdam, 1973. With an appendix by J. Tate. MR 0409362 M. Ram Murty, "On Artin’s conjecture," J. Number Theory, v. 16, 1983, pp. 147-168.
- 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
- 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
- John T. Tate, The arithmetic of elliptic curves, Invent. Math. 23 (1974), 179–206. MR 419359, DOI 10.1007/BF01389745
Additional Information
- © Copyright 1989 American Mathematical Society
- Journal: Math. Comp. 53 (1989), 415-430
- MSC: Primary 11G05; Secondary 11A51, 11Y11
- DOI: https://doi.org/10.1090/S0025-5718-1989-0970701-9
- MathSciNet review: 970701