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
MathSciNet review: 946604
Full-text PDF

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?)

Similar Articles

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

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

Additional Information

Article copyright: © Copyright 1989 American Mathematical Society

American Mathematical Society