Cette thèse propose des améliorations aux problèmes de la multiplication et de la factorisation d'entier. <p> L'algorithme de Schönhage-Strassen pour la multiplication d'entier, publié en 1971, fut le premier à atteindre une complexité de O(n log (n) log(log(n))) pour multiplier deux entiers de n bits, et reste parmi les plus rapides en pratique. Il réduit la multiplication d'entier à celle de polynôme sur un anneau fini, en utilisant la transformée de Fourier rapide pour calculer le produit de convolution. Dans un travail commun avec Gaudry et Zimmermann, nous décrivons une implantation efficace de cet algorithme, basée sur la bibliothèque GNU MP; par rapport aux travaux antérieurs, nous améliorons l'utilisation de la mémoire cache, la sélection des paramètres et la longueur de convolution, ce qui donne un gain d'un facteur 2 environ. <p> Les algorithmes P-1 et P+1 trouvent un facteur p d'un entier composé rapidement si p-1, respectivement p+1, ne contient pas de grand facteur premier. Ces algorithmes comportent deux phases: la première phase calcule une grande puissance g<sub>1</sub> d'un élément g<sub>0</sub> d'un groupe fini défini sur F<sub>p</sub>, respectivement F<sub>p^2</sub>, la seconde phase cherche une collision entre puissances de g<sub>1</sub>, qui est trouvée de manière efficace par évaluation-interpolation de polynômes. Dans un travail avec Peter Lawrence Montgomery, nous proposons une amélioration de la seconde phase de ces algorithmes, avec une construction plus rapide des polynômes requis, et une consommation mémoire optimale, ce qui permet d'augmenter la limite pratique pour le plus grand facteur premier de p-1, resp. p+1, d'un facteur 100 environ par rapport aux implantations antérieures. <p> Le crible algébrique (NFS) est le meilleur algorithme connu pour factoriser des entiers dont les facteurs n'ont aucune propriété permettant de les trouver rapidement. En particulier, le module du système RSA de chiffrement est choisi de telle sorte, et sa factorisation casse le système. De nombreux efforts ont ainsi été consentis pour améliorer NFS, de façon à établir précisément la sécurité de RSA. Nous donnons un bref aperçu de NFS et de son historique. Lors de la phase de crible de NFS, de nombreux petits entiers doivent être factorisés. Nous présentons en détail une implantation de P-1, P+1, et de la méthode ECM basée sur les courbes elliptiques, qui est optimisée pour de tels petits entiers. Finalement, nous montrons comment les paramétres de ces algorithmes peuvent étre choisis finement, en tenant compte de la distribution des facteurs premiers dans les entiers produits par NFS, et de la probabilité de trouver des facteurs premiers d'une taille donnée.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00477005 |
| Date | 28 January 2010 |
| Creators | Kruppa, Alexander |
| Publisher | Université Henri Poincaré - Nancy I |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0017 seconds