Elliptic Pseudoprime

Let E be an elliptic curve defined over the field of rationals Q(sqrt(-d)) having equation


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=0 (mod n),

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

See also

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

Explore with Wolfram|Alpha


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 Number Theory--Théorie des nombres:Proceedings of the International Number Theory Conference Held at Université Laval in 1987 (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.

Referenced on Wolfram|Alpha

Elliptic Pseudoprime

Cite this as:

Weisstein, Eric W. "Elliptic Pseudoprime." From MathWorld--A Wolfram Web Resource.

Subject classifications