Skip to Main content Skip to Navigation

Elliptic curves and primality proving

Abstract : This report describes the theory and implementation of the Elliptic Curve Primality Proving algorithm - ECPP - algorithm. This includes the relationships between representing primes by quadratic forms and the explicit construction of class fields of imaginary quadratic fields ; the theory of elliptic curves with complex multiplication over the field of complex numbers as well as over finite fields. We then use this theory to design a very powerful primality proving algorithm. Half of the paper is devoted to the description of its implementation. In particular, we give the currently best algorithms to speed up each part of the program. The resulting program is very fast. We can prove the primality of 100-digit numbers in less than five minutes on a SUN 3/60 workstation, and we can treat all numbers with less than 1000 digits in a reasonable amount of time using a distributed implementation.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 5:54:21 PM
Last modification on : Thursday, February 11, 2021 - 2:50:07 PM
Long-term archiving on: : Sunday, April 4, 2010 - 9:55:52 PM


  • HAL Id : inria-00075302, version 1



A.O.L. Atkin, F. Morain. Elliptic curves and primality proving. RR-1256, INRIA. 1990. ⟨inria-00075302⟩



Record views


Files downloads