Le site d'ECPP
English version
Présentation générale
ECPP est un paquetage contenant un programme de preuve de
primalité, correspondant à l'implantation des articles
donnés en référence.
Foire Aux Questions concernant ECPP
Comment obtenir le paquetage ?
Cliquez ici et suivez la procédure.
Que veut dire ECPP?
ECPP est l'acronyme de Elliptic Curve Primality Proving.
Pourquoi aurais-je besoin d'ECPP?
Prouver la primalité d'un entier donné est une des
tâches élémentaires de la théorie des
nombres. Le programme peut être utilisé pour construire
des nombres premiers cryptographiques.
Pourquoi ECPP est-il supérieur aux algorithmes de test de
primalité ?
Les algorithmes de test de primalité, comme l'algorithme de
Dubois-Selfridge-Miller-Rabin, s'arrêtent avec la réponse
Oui, ce nombre est composé
ou
Je n'ai trouvé aucune raison pour laquelle ce nombre ne
devrait pas être premier.
Dans ce dernier cas, il y a un risque qu'un nombre composé soit
déclaré premier. Les algorithmes de primalité
exacte fournissent une preuve que le nombre est bien premier. Cette
preuve est appelée certificat de primalité.
Qu'est-ce qu'un certificat de primalité ?
Le programme produit une longue liste de nombres qui forment une
preuve de primalité pour un entier. En bref, le programme
construit une suite décroissante de nombres premiers
intermédiaires, la primalité du plus petit entrainant
celle du plus grand. Le certificat peut être
vérifié soit par le programme checkcertif faisant
partie du paquetage, ou par tout autre programme écrit
indépendamment. Un exemple est donné en Maple.
Pourquoi ECPP est-il supérieur aux autres algorithmes de
primalité exacte?
Le seul concurrent sérieux d'ECPP est le test utilisant les
sommes de Jacobi, et dû à H. Cohen
et H. W. Lenstra, Jr.. Il a été implanté par
H. Cohen et A. K. Lenstra. Dans cet algorithme, la primalité se
réduit à un énorme calcul dans une extension
d'anneaux de degré élevé. Prouver la
primalité ou vérifier le certificat prend à peu
près le même temps et requiert une implantation
très soignée. Dans ECPP, la partie vérification
se fait en temps polynomial et en pratique elle prend beaucoup moins
de temps que le programme de construction. De plus, elle est
très simple à programmer (jetez un oeil au programme
checkcertif.map).
Quels sont les plus grands entiers dont la primalité ait été prouvée par votre implantation d'ECPP ?
Il s'agit de:
- 010903: 907^694+694^907 (2578 chiffres décimaux) avec ECPP-V11.0.5alpha.
- 010828: 903^376+376^903 (2326 chiffres décimaux) avec ECPP-V11.0.5alpha.
- 010727: 883^394+394^883 (2292 chiffres décimaux) avec ECPP-V11.0.5alpha.
- (2^7331-1)/458072843161 (2196 chiffres décimaux),
trouvé par E. Mayer et
F. Morain avec ECPP, octobre
1997, en un mois de CPU sur une Alpha 400MHz.
- (2^5689-1) / 919724609777 (1701 chiffres décimaux)
par E. Mayer avec mon programme en
150 heures sur une Alpha 400 MHz en octobre 1997.
- (2^5227-1) / (1129033 * 47126633 * 227482218017) (1549
chiffres) par E. Mayer.
- (2^5087-1) / (40697 * 1678711 * 114097014833) (1510
chiffres) par E. Mayer.
-
p(1840926) (nombre de 1505 chiffres décimaux contenant le
nombre d'écritures de 1840926 comme somme d'entiers positifs),
calcul fait en 1992.
ECPP peut-il vraiment prouver la primalité de tous les
entiers de 2578 chiffres décimaux ?
Bien sûr! Du moins en théorie. En fait, il me faut
être un peu plus prudent. Le paquetage contient un nombre fini
de données utilisables pour prouver la primalité d'un
entier. En cas de problèmes (nombre difficile), ce stock de
données ne suffira pas. C'est pourquoi la version actuelle
contient un mécanisme de backtrack qui permet de tester plus
facilement plus de nombres. L'explication de ce mécanisme sera
raconté bientôt ailleurs. Dans mon expérience,
ECPP n'échoue pas pour des nombres de moins de 500 chiffres
décimaux. Le lecteur/testeur du programme peut m'envoyer des
nombres non faisables de moins de 500 chiffres s'il en trouve.
Où puis-je trouver des références
complémentaires?
- Pour (fast)ECPP
- Morain, F.
Easy numbers for the Elliptic Curve Primality Proving
algorithm.
In ISSAC '92 (New York, 1992), P. S. Wang, Ed., ACM Press,
pp. 263-268.
Proceedings, July 27-29, Berkeley.
[ bib |
.ps.gz ]
-
A. O. L. Atkin and François Morain.
Elliptic curves and primality proving.
Math. Comp., 61(203):29--68, July 1993.
-
F. Morain
Primality proving using elliptic curves: an update.
In J. P. Buhler, editor, Algorithmic Number Theory, volume 1423
of Lecture Notes in Comput. Sci., pages 111--127. Springer-Verlag,
1998. Third International Symposium, ANTS-III, Portland, Oregon, june 1998,
Proceedings.
- Enge, A., and Morain, F.
Comparing invariants for class fields of imaginary quadratic fields.
In Algorithmic Number Theory (2002), C. Fieker and D. R.
Kohel, Eds., vol. 2369 of Lecture Notes in Comput. Sci.,
Springer-Verlag, pp. 252-266.
5th International Symposium, ANTS-V, Sydney, Australia, July 2002,
Proceedings.
[ bib |
.ps.gz ]
- Franke, J., Kleinjung, T., Morain, F., and Wirth, T.
Proving the primality of very large numbers with fastecpp.
In Algorithmic Number Theory (2004), D. Buell, Ed., vol. 3076
of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 194-207.
6th International Symposium, ANTS-VI, Burlington, VT, USA, June 2004,
Proceedings.
[ bib |
http ]
- Morain, F.
Computing the cardinality of CM elliptic curves using torsion
points.
J. Théor. Nombres Bordeaux 19, 3 (2007), 663-681.
[ bib |
.pdf ]
- Morain, F.
Implementing the asymptotically fast version of the elliptic curve
primality proving algorithm.
Math. Comp. 76 (2007), 493-505.
[ bib |
.pdf ]
- Pour la théorie de Galois utilisée dans ECPP
- Hanrot, G., and Morain, F.
Solvability by radicals from an algorithmic point of view.
In Symbolic and algebraic computation (2001), B. Mourrain,
Ed., ACM, pp. 175-182.
Proceedings ISSAC'2001, London, Ontario.
[ bib |
.ps.gz ]
- Enge, A., and Morain, F.
Fast decomposition of polynomials with known Galois group.
In Applied Algebra, Algebraic Algorithms and Error-Correcting
Codes (2003), M. Fossorier, T. Høholdt, and A. Poli, Eds., vol. 2643 of
Lecture Notes in Comput. Sci., Springer-Verlag, pp. 254-264.
15th International Symposium, AAECC-15, Toulouse, France, May 2003,
Proceedings.
[ bib |
.ps.gz |
.ps.gz ]
- Pour la méthode CM
- Morain, F.
Building cyclic elliptic curves modulo large primes.
In Advances in Cryptology - EUROCRYPT '91 (1991), D.
Davies, Ed., vol. 547 of Lecture Notes in Comput. Sci.,
Springer-Verlag, pp. 328-336.
Proceedings of the Workshop on the Theory and Application of
Cryptographic Techniques, Brighton, United Kingdom, April 8-11, 1991.
[ bib ]
- Dupont, R., Enge, A., and Morain, F.
Building curves with arbitrary small MOV degree over finite prime
fields.
J. of Cryptology 18, 2 (2005), 79-89.
[ bib ]
Voir également ma page web.