A class of algorithm, abbreviated ECPP, which provides certificates of primality using sophisticated results from the theory of Elliptic Curves. A detailed description and list of references are given by Atkin and Morain (1990, 1993).

Adleman and Huang (1987) designed an independent algorithm using elliptic curves of genus two.

**References**

Adleman, L. M. and Huang, M. A. ``Recognizing Primes in Random Polynomial Time.'' In *Proc. 19th STOC,
New York City, May 25-27, 1986.* New York: ACM Press, pp. 462-469, 1987.

Atkin, A. O. L. Lecture notes of a conference, Boulder, CO, Aug. 1986.

Atkin, A. O. L. and Morain, F. ``Elliptic Curves and Primality Proving.'' Res. Rep. 1256, INRIA, June 1990.

Atkin, A. O. L. and Morain, F. ``Elliptic Curves and Primality Proving.'' *Math. Comput.* **61**, 29-68, 1993.

Bosma, W. ``Primality Testing Using Elliptic Curves.'' Techn. Rep. 85-12, Math. Inst., Univ. Amsterdam, 1985.

Chudnovsky, D. V. and Chudnovsky, G. V. ``Sequences of Numbers Generated by Addition in Formal Groups and New Primality and Factorization Tests.'' Res. Rep. RC 11262, IBM, Yorktown Heights, NY, 1985.

Cohen, H. *Cryptographie, factorisation et primalité: l'utilisation des courbes elliptiques.*
Paris: C. R. J. Soc. Math. France, Jan. 1987.

Kaltofen, E.; Valente, R.; and Yui, N. ``An Improved Las Vegas Primality Test.'' Res. Rep. 89-12, Rensselaer Polytechnic Inst., Troy, NY, May 1989.

© 1996-9

1999-05-25