Elliptic Pseudoprime

Let $E$ be an Elliptic Curve defined over the Field of Rational Numbers $\Bbb{Q}(\sqrt{-d}\,)$ having equation

$$y^2 = x^3 + ax + b$$

with $a$ and $b$ Integers. Let $P$ be a point on $E$ with integer coordinates and having infinite order in the additive group of rational points of $E$, and let $n$ be a Composite Natural Number such that $(-d/n)=-1$, where $(-d/n)$ is the Jacobi Symbol. Then if

$$(n+1)P\equiv 0\ \left({{\rm mod\ } {n}}\right),$$

$n$ is called an elliptic pseudoprime for $(E,P)$.

See also Atkin-Goldwasser-Kilian-Morain Certificate, Elliptic Curve Primality Proving, Strong Elliptic Pseudoprime

References

Balasubramanian, R. and Murty, M. R. ``Elliptic Pseudoprimes. II.'' In Séminaire de Théorie des Nombres, Paris 1988-1989 (Ed. C. Goldstein). Boston, MA: Birkhäuser, pp. 13-25, 1990.

Gordon, D. M. ``The Number of Elliptic Pseudoprimes.'' Math. Comput. 52, 231-245, 1989.

Gordon, D. M. ``Pseudoprimes on Elliptic Curves.'' In Théorie des nombres (Ed. J. M. DeKoninck and C. Levesque). Berlin: de Gruyter, pp. 290-305, 1989.

Miyamoto, I. and Murty, M. R. ``Elliptic Pseudoprimes.'' Math. Comput. 53, 415-430, 1989.

Ribenboim, P. The New Book of Prime Number Records, 3rd ed. New York: Springer-Verlag, pp. 132-134, 1996.