Courbes elliptiques et tests de primalité / François Morain ; sous la direction de Jean-Louis Nicolas

Bibliogr. p. 184-186

Thèse de doctorat mathématiques 1990 université Claude Bernard (Lyon)

NOUS DECRIVONS DANS CETTE THESE L'APPLICATION DE LA THEORIE DES COURBES ELLIPTIQUES DEFINIES SUR LES CORPS FINIS A LA CONSTRUCTION D'ALGORITHMES EFFICACES DE PRIMALITE EXACTE. NOUS FAISONS LE LIEN ENTRE LE PROBLEME DE LA REPRESENTATION DES NOMBRES PREMIERS PAR DES FORMES QUADRATIQUES BINAIRES ET LA THEORIE DU CORPS DE CLASSE. A CE PROPOS, NOUS DONNONS UN ALGORITHME RAPIDE DE CONSTRUCTION DU CORPS DE CLASSE D'UN CORPS QUADRATIQUE IMAGINAIRE A L'AIDE DES FONCTIONS DE WEBER. NOUS EN DEDUISONS LE CALCUL DES INVARIANTS DES COURBES ELLIPTIQUES A MULTIPLICATION COMPLEXE DANS UN CORPS FINI EN RESOLVANT PAR RADICAUX L'EQUATION DE DEFINITION DU CORPS DE CLASSE, DANS LE CORPS DES COMPLEXES D'ABORD, MODULO UN NOMBRE PREMIER ENSUITE. NOUS MONTRONS COMMENT GENERALISER LES ALGORITHMES DE PREUVE DE PRIMALITE LES PLUS CLASSIQUES (RECIPROQUES DU THEOREME DE FERMAT) EN UTILISANT LES COURBES ELLIPTIQUES. A L'ENCONTRE DE SON CONCURRENT LE PLUS SERIEUX (SOMMES DE JACOBI), L'ALGORITHME QUI EN RESULTE PRODUIT UN CERTIFICAT DE PRIMALITE. D'UN POINT DE VUE PRATIQUE, NOUS DETAILLONS TOUTES LES PHASES DE L'IMPLANTATION DE L'ALGORITHME, D'ABORD SUR UNE STATION DE TRAVAIL, PUIS SUR PLUSIEURS STATIONS D'UNE MANIERE DISTRIBUEE. A CHAQUE ETAPE, NOUS PRESENTONS LES MEILLEURS ALGORITHMES CONNUS POUR RESOUDRE CHAQUE PROBLEME PARTICULIER (CALCULS SUR LES COURBES ELLIPTIQUES, RECHERCHE DE RACINES DE POLYNOMES MODULO UN NOMBRE PREMIER, ...). NOUS DECRIVONS EGALEMENT L'UTILISATION D'UN MULTIPLICATEUR HARDWARE POUR LE CALCUL DU PRODUIT DE GRANDS ENTIERS, QUI PERMET D'ACCELERER CONSIDERABLEMENT LES CALCULS. ENFIN, NOUS UTILISONS LE PROGRAMME POUR LA RECHERCHE DE NOMBRES PREMIERS DE CENT CHIFFRES (UTILES EN CRYPTOGRAPHIE) ET POUR LA CERTIFICATION DE NOMBRES DE TROIS CENTS A TROIS MILLE CHIFFRES