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.
Type de document :
RR-1256, INRIA. 1990
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 17:54:21
Dernière modification le : vendredi 16 septembre 2016 - 15:11:33
Document(s) archivé(s) le : dimanche 4 avril 2010 - 21:55:52



  • HAL Id : inria-00075302, version 1



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



Consultations de la notice


Téléchargements de fichiers