Elliptic pseudoprimes

Authors:
I. Miyamoto and M. Ram Murty

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

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 *n*th 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*.

- 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$," - 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 https://doi.org/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 https://doi.org/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 https://doi.org/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, - 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," - Carl Pomerance,
*On the distribution of pseudoprimes*, Math. Comp.**37**(1981), no. 156, 587–593. MR**628717**, DOI https://doi.org/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** - John T. Tate,
*The arithmetic of elliptic curves*, Invent. Math.**23**(1974), 179–206. MR**419359**, DOI https://doi.org/10.1007/BF01389745

*Indag. Math.*, v. 13, 1951, pp. 50-60.

*Sieve Methods*, Academic Press, London, 1974.

*J. Number Theory*, v. 16, 1983, pp. 147-168.

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

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

Additional Information

Article copyright:
© Copyright 1989
American Mathematical Society