Les méthodes de factorisation d'entiers se répartissent en deux classes. La première est formée d'algorithmes dont le succès dépend du nombre à factoriser. Plus précisément, leur temps de calcul est une fonction de la taille du facteur à trouver. Ces méthodes se prêtent donc pour les nombres qui ont de petits facteurs, même lorsque les nombres quant à eux sont grands. Citons l'algorithme p-1 de Pollard, la méthode des courbes elliptiques de Lenstra [Lenstra87]. La seconde classe comprend les algorithmes dits tous-usages, qui peuvent factoriser n'importe quel entier en un temps donné. Les algorithmes les plus performants à ce jour sont ceux du crible quadratique et du crible algébrique, voir [LeLe93].
Le LIX s'est illustré dans la factorisation de nombres pris dans le Challenge RSA (c'est par exemple le cas de RSA-155) aussi bien que dans le projet Cunningham.
Pour en savoir plus:Là encore les algorithmes utilisés sont de deux types. Le premier est celui des algorithmes de composition, qui permettent de donner une preuve qu'un nombre est composé, mais ne permettent pas de prouver qu'un nombre est premier. Ce premier groupe comprend les algorithmes de Fermat, Solovay-Strassen, Dubois-Selfridge-Miller-Rabin, etc. La seconde catégorie est celle des algorithmes de preuve de primalité qui eux fournissent une preuve que le nombre est premier ou non. Il existe deux algorithmes couramment utilisés dans cette classe : les sommes de Jacobi [CoLe84] et ECPP [AtMo93b]. Ces deux algorithmes ne sont pas rendus obsolètes par le récent algorithme AKS.
Pour en savoir plus:Pour calculer des logarithmes discrets dans F2n, on utilise des algorithmes sous-exponentiels basés sur le calcul d'index. Plus particulièrement, l'algorithme de Coppersmith a été utilisé au LIX par Thomé pour réaliser des calculs dans le corps F2607, taille qui constitue un record dans le domaine. Les calculs pour arriver à ce résultat se sont étendu sur plusieurs mois, mais en utilisant des ordinateurs "standard", démontrant ainsi la faisabilité de ce genre de calculs sans accès à des supercalculateurs (d'anciens records de logarithme discret avaient été réalisés grâce à des supercalculateurs).
Savoir calculer des logarithmes discrets dans des corps de caractéristique 2, ou du moins avoir une idée de la limite entre le faisable et l'infaisable permet aussi de se prononcer sur la sécurité de certaines courbes elliptiques dites supersingulières sur des corps de caractéristique 2, car le problème du logarithme discret sur de telles courbes peut être ramené à un calcul de logarithme discret sur F2n.
Pour en savoir plus: