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:

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? Voir également ma page web.