Nombres entiers et corps finis

Factorisation d'entiers

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.

[Morain02]

F. Morain. La factorisation d'entiers. Dans le dossier hors-série de Pour la Science L'art du secret, juillet/octobre 2002, 62-64.

[Lenstra87]

Hendrik W. Lenstra, Jr. Factoring integers with elliptic curves. Annals of Math., 126:649--673, 1987.

[AtGrLeLe94]

Derek Atkins, Michael Graff, Arjen K. Lenstra, and Paul C. Leyland. The magic words are squeamish ossifrage. In Josef Pieprzyk and Reihanah Safavi-Naini, editors, Advances in Cryptology - ASIACRYPT '94, volume 917 of Lecture Notes in Comput. Sci., pages 263-277. Springer-Verlag, 1995. 4th International Conference on the Theory and Applications of Cryptology, Wollongong, Australia, November/December 1994, Proceedings.

[LeLe93]

A. K. Lenstra and H. W. Lenstra, Jr., editors. The development of the number field sieve, volume 1554 of Lecture Notes in Math. Springer, 1993.

[RSA155]

S. Cavallar et al. Factorization of a 512-bit RSA modulus. Proc. EUROCRYPT 2000, LNCS.

Primalité

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.

[AtMo93b]

A. O. L. Atkin and F. Morain. Elliptic curves and primality proving. Math. Comp., 61(203):29-68, 1993.

[CoLe84]

H. Cohen and H. W. Lenstra, Jr. Primality testing and Jacobi sums. Math. Comp., 42(165):297-330, 1984.

Logarithme discret dans F_2ⁿ

Pour calculer des logarithmes discrets dans F_2ⁿ, 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 F_2⁶⁰⁷, 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 F_2ⁿ.

[Thomé01b]

E. Thomé. Computation of discrete logarithms in F_2⁶⁰⁷. Proc. ASIACRYPT '2001, LNCS 2248.

[Coppersmith84]

D. Coppersmith. Fast evaluation of logarithms in fields of characteristic two. IEEE Trans. Inform. theory 30(4):587-594, 1984.

[GoMc93]

D. M. Gordon and K. S. McCurley. Massively parallel computation of discrete logarithms. Proc. CRYPTO '92, LNCS 740

[JoLe02]

A. Joux and R. Lercier. The function field sieve is quite special. Proc. ANTS-V, LNCS, July 2002.