Crible algébrique

En théorie des nombres, l'algorithme du crible du corps de nombres généralisé^{[Note 1]}^,^{[Note 2]} (GNFS) obtient la décomposition d'un entier en produit de facteurs premiers. C'est à l'heure actuelle (2018) l'algorithme le plus efficace connu pour obtenir cette décomposition, lorsque le nombre considéré est assez grand^{[Note 3]}, c'est-à-dire au-delà d'environ 10¹⁰⁰, et ne possède pas de structure remarquable^{[Note 4]}. Cette efficacité est due pour partie à l'utilisation d'une méthode de crible et pour partie à l'utilisation d'algorithmes efficaces pour certaines opérations (comme la manipulation de matrices creuses). La complexité algorithmique du crible de corps de nombres n'est pas prouvée, elle n'est qu'heuristique^{[Note 5]}. Cette estimation est utilisée par les organismes de standardisation tels que le NIST pour fixer des tailles des clés RSA à un niveau de sécurité donné.

De manière remarquable, l'algorithme permet également (au prix de modifications simples) de calculer des logarithmes discrets dans les corps finis, avec la même complexité. C'est à l'heure actuelle (2018) l'algorithme le plus efficace connu dans les corps finis de caractéristique première très grande^{[Note 6]}. En revanche, l'algorithme du crible du corps de nombres n'est pas applicable au calcul du logarithme discret dans un groupe abstrait générique, ce qui est une des motivations derrière la cryptographie sur les courbes elliptiques.

Pour ces raisons, l'algorithme est responsable aujourd'hui de nombreux records de factorisation (et de calculs de logarithmes discrets) et joue un rôle important en cryptographie. Enfin, quoique de manière plus anecdotique, il intervient également dans le contexte plus large de la sécurité informatique, par exemple dans l'attaque Logjam dont il est un composant essentiel^[1] : les auteurs ont montré comment intercepter une communication TLS 1.2, une des étapes consistant à calculer au moyen du crible du corps de nombres un logarithme discret dans un corps de 512 bits en moins d'une minute.

Histoire

L'algorithme du crible du corps de nombres est une des techniques de factorisation développées progressivement au cours du 20^e siècle.

Il fut proposé initialement dans une lettre de John Pollard à Arjen Lenstra et Andrew Odlyzko datée de 1988^[2], comme une amélioration possible du crible quadratique. L'ayant testé sur le septième nombre de Fermat (factorisé pour la première fois en 1970), l'algorithme est étendu puis publié par Lenstra, Lenstra, Manasse et Pollard en 1990^[3]^,^[4] dans une version « restreinte » à certains types d'entiers. Cette première version était tout de même suffisante pour factoriser pour la première fois le neuvième nombre de Fermat avec les ressources disponibles à l'époque^[5]. Des travaux successifs et les contributions de Joe Buhler et Carl Pomerance ont permis d'étendre l'algorithme à des entiers arbitraires^[6]^,^[7]. L'algorithme du crible du corps de nombres généralisé a atteint sa forme actuelle au courant des années 1990, sous l'impulsion entre autres de Peter Montgomery, mais il a continué à bénéficier depuis de l'amélioration des capacités de calcul des ordinateurs, et de la disponibilité accrue du calcul distribué^[8].

L'algorithme fut simultanément adapté pour calculer des logarithmes discrets^[9], où il reste aujourd'hui l'algorithme le plus efficace connu pour résoudre ce problème sur les corps finis de grande caractéristique. En petite caractéristique, plusieurs optimisations sont possibles, comme l'algorithme du crible de corps de fonctions (function field sieve) développé initialement par Adleman en 1994^[10].

En 1995, Peter Shor présente un algorithme quantique dont la complexité asymptotique est très inférieure à celle du crible du corps de nombres, basé sur une approche radicalement différente ; toutefois un tel algorithme nécessite un calculateur quantique suffisamment grand pour fonctionner, ce qu'à l'heure actuelle (2018) on ne sait pas construire.

Principe d'opération

Principe général

À l'instar du crible quadratique dont il est une amélioration, l'algorithme du crible du corps de nombres fonctionne en deux phases principales^{[Note 7]}^,^[11] :

Une phase de collecte, hautement parallélisable, pendant laquelle l'algorithme recherche des nombres friables modulo l'entier n à factoriser. C'est au cours de cette étape que la technique de crible est utilisée, s'appuyant sur les propriétés des corps de nombres pour sélectionner efficacement des candidats. Les nombres retenus à l'issue de cette première phase se décomposent tous en produits de puissances d'une base de facteurs (en général premiers). L'efficacité du crible du corps de nombres est surtout due à cette technique de crible, qui permet de trouver des nombres friables plus rapidement que d'autres approches telles que le crible quadratique.
Une phase d'algèbre linéaire, difficilement parallélisable, au cours de laquelle l'algorithme construit un élément du noyau d'une grande matrice creuse. Les lignes de cette matrice correspondent aux puissances (modulo 2) de chaque facteur de la base apparaissant dans les nombres collectés dans la phase précédente. Le vecteur du noyau ainsi obtenu permet de déterminer une congruence de carrés, qui donne immédiatement une factorisation de n.

Cette seconde phase n'est pas spécifique au crible du corps de nombres, mais nécessite des algorithmes capables de manipuler des matrices de grande taille. L'algorithme de Lanczos par blocs ou celui de Wiedemann (dû à Coppersmith^[12]^,^[13]) sont souvent employés.

Phase de collecte

On note $n$ l'entier positif que l'on cherche à factoriser, et on suppose que $n$ n'est pas la puissance d'un nombre premier (cette précaution n'est pas un renoncement : dans le cas contraire où $n=p^{k}$ il est aisé de factoriser en calculant des racines).

Principe du crible

Le crible du corps de nombres s'appuie sur la remarque suivante. Soit $f$ un polynôme unitaire, à coefficients entiers, irréductible sur $\mathbb {Z}$ . Notons $\alpha$ une racine complexe de $f$ . Supposons qu'il existe $m$ tel que $f(m)=0{\bmod {n}}$ , alors il existe un morphisme d'anneaux $\phi :\mathbb {Z} [\alpha ]\to \mathbb {Z} /(n)$ défini par $\phi :\alpha \mapsto m$ . En particulier, pour tout polynôme $g$ à coefficients entiers, on a $\phi (g(\alpha ))=g(m){\bmod {n}}$ . Voici comment cette remarque participe à la recherche de congruences de carrés : si on a trouvé une collection ${\mathcal {S}}$ de polynômes tels que $\prod _{g\in {\mathcal {S}}}g(\alpha )$ est un carré dans $\mathbb {Z} [\alpha ]$ , notons-le $\beta ^{2}$ , et que

$\prod _{g\in {\mathcal {S}}}g(m)$ est un carré dans $\mathbb {Z} /(n)$ , notons-le $y^{2}$ . Alors on a trouvé une relation :

$x^{2}=\phi (\beta )^{2}=\phi (\beta ^{2})=\phi \left(\prod _{g\in {\mathcal {S}}}g(\alpha )\right)=\prod _{g\in {\mathcal {S}}}g(m)=y^{2}{\bmod {n}}$ Pour trouver ${\mathcal {S}}$ , on va à l'instar du crible quadratique ou de la méthode de Dixon, chercher des nombres friables. Seulement, pour cela, il faut d'abord définir une notion de friabilité sur $\mathbb {Z} [\alpha ]$ . Avant de détailler cet aspect, donnons une manière de construire les polynômes $f$ et $g$ intervenant dans l'équation.

Polynômes f et g

Pour construire le polynôme $f$ de la section précédente, on peut utiliser ceci : prenons $d$ un entier tel que $n>2^{d^{2}}$ et posons $m=\lfloor n^{1/d}\rfloor$ . En écrivant l'entier $n$ en base $m$ , on obtient

$n=c_{d}m^{d}+c_{d-1}m^{d-1}+\cdots +c_{0}$ et on définit

$f(t)=c_{d}t^{d}+c_{d-1}t^{d-1}+\cdots +c_{0}$

On vérifie aisément que $f$ est unitaire, et que $f(m)=n$ par construction, donc $f(m)=0{\bmod {n}}$ . Si $f$ n'est pas irréductible, on peut le décomposer en facteurs irréductibles de manière efficace^{[Note 8]}.

Pour construire les polynômes $g$ , posons de manière heuristique $g(t)=a-bt$ pour $a,b$ deux entiers premiers entre eux avec $0<b,|a|<B$ .

Friabilité sur ℤ[α]

Si $\mathbb {Z} [\alpha ]$ était un anneau factoriel, on pourrait simplement décomposer ses éléments en facteurs premiers et chercher les entiers friables de l'anneau pour trouver $\beta$ . Malheureusement, ce n'est en général pas le cas. Cela dit, on dispose de l'application norme $N:\mathbb {Q} (\alpha )\to \mathbb {Q}$ qui est multiplicative et dont les valeurs sur $\mathbb {Z} [\alpha ]$ sont entières^{[Note 9]}. En particulier, si $\prod _{(a,b)\in {\mathcal {S}}}(a-b\alpha )$ est un carré dans $\mathbb {Z} [\alpha ]$ , alors $\prod _{(a,b)\in {\mathcal {S}}}N(a-b\alpha )$ est un carré dans $\mathbb {Z}$ ^{[Note 10]}, et plus généralement un élément qui se décompose en de nombreux facteurs aura une norme qui se décompose elle-même en de nombreux facteurs.

On dira qu'un élément $u$ de $\mathbb {Z} [\alpha ]$ est « friable » lorsque $N(u)$ est friable. La phase de collecte consiste donc à chercher des couples $(a,b)$ tels que $g(\alpha )=a-b\alpha \in \mathbb {Z} [\alpha ]$ est friable en ce sens.

Phase d'algèbre linéaire

La phase d'algèbre linéaire consiste, une fois que l'on dispose de suffisamment de relations entre nombres friables, à construire une congruence de carrés. Pour cela, on représente un nombre friable sur la base de friabilité, c'est-à-dire $u=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}$ où ${\mathcal {P}}=\{p_{1},\cdots ,p_{k}\}=\{p~{\textrm {premier}},p<B\}$ , par le vecteur de ses exposants : $v(u)={\begin{pmatrix}e_{1}&e_{2}&\cdots &e_{k}\end{pmatrix}}$ . Ensemble, tous les nombres collectés forment une matrice, dont on cherche un élément du noyau modulo 2, c'est-à-dire une combinaison linéaire des lignes telle que le vecteur obtenu ait des coefficients pairs.

Cette combinaison linéaire d'exposants correspond à un produit entre les nombres collectés : d'un côté, il s'agit de carrés (donc leur produit est encore un carré modulo $n$ ), et de l'autre, il s'agit de nombres dont le produit a des exposants pairs dans la base de friabilité, c'est-à-dire encore des carrés. On a bien une congruence de carrés.

Complexité de l'algorithme

L'analyse de la complexité de l'algorithme repose notamment sur l'estimation de la distribution des nombres friables. Ce problème a été étudié par de Bruijn^[14], et Canfield-Erdös-Pomerance^[15], qui montrent le résultat suivant :

« Un entier positif choisi au hasard plus petit que

L_{x}[r,\psi ]

est

L_{x}[s,\beta ]

-friable avec probabilité

L_{x}\left[r-s,-{\frac {\psi (r-s)}{\beta }}\right]

lorsque

x\to \infty

. »

Dans l'énoncé ci-dessus on utilise la notation L (introduite par Pomerance en 1982^[16]), et on note dans la suite $\pi (B)$ le nombre d'entiers positifs premiers inférieurs à $B$ . Une analyse globale donne alors une complexité^{[Note 11]} :

$\underbrace {\left(\pi (L_{n}[s,\beta ])+\omega \right)} _{\mathrm {nombre~de~relations~{\grave {a}}~collecter} }\cdot \underbrace {L_{n}[r-s,\psi (r-s)/\beta ]} _{\mathrm {inverse~de~proba~de~friabilite} }\cdot \underbrace {S\left(L_{n}[r,\psi ],L_{n}[s,\beta ]\right)} _{\mathrm {cout~verification~friabilite} }+\underbrace {M\left(\pi (L_{n}[s,\beta ])\right)} _{\mathrm {cout~algebre~lineaire} }$

L'utilisation des meilleurs algorithmes d'algèbre linéaire et l'amortissement du coût de $S$ grâce au crible permettent, en optimisant tous les paramètres, d'estimer la probabilité totale de l'algorithme à $L_{n}\left[{\frac {1}{3}},{\sqrt[{3}]{\frac {64}{9}}}\right]$ ^{[Note 12]}. Il est possible d'abaisser encore cette complexité au moins en principe en utilisant deux techniques dues à Coppersmith^[17], mais les gains réels de ces modifications ne sont pas encore bien mesurés^{[Note 13]}.

Adaptation au calcul de logarithme discret

De même que la méthode de Dixon^[18]^,^[19], le crible du corps de nombres s'adapte bien au calcul de logarithmes discrets. En particulier, il s'agit du plus efficace algorithme classique connu pour résoudre ce problème dans les corps finis, où le crible du corps de nombres s'apparente à une forme de « calcul d'indice »^[9].

Records obtenus au moyen de cet algorithme

Le crible du corps de nombres est derrière de nombreux records récents de factorisation et de calculs de logarithmes discrets.

Factorisation de nombres de forme générale

2 Décembre 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, et Paul Zimmermann, factorisation du nombre RSA RSA-240, d'une taille de 795 bits^[20].

6 janvier 2010, Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen Lenstra, Emmanuel Thomé, Joppe Bos, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev et Paul Zimmermann, factorisation du nombre RSA RSA-768, d'une taille de 768 bits^[21].

Factorisation de nombres de forme particulière

4 août 2012, Greg Childers, factorisation du nombre de Mersenne 2¹⁰⁶¹ − 1 d'une taille de 1061 bits^[22].

Logarithmes discrets dans un corps de grande caractéristique

2 Décembre 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, et Paul Zimmermann, logarithme discret modulo un premier sûr de 795 bits^[20].

16 juin 2016, Thorsten Kleinjung, Claus Diem, Arjen K. Lenstra, Christine Priplata et Colin Stahlke, logarithme discret modulo un premier sûr de 768 bits^[23].

11 juin 2014, Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli et Emmanuel Thomé, logarithme discret modulo un premier sûr de 596 bits.
5 février 2007, Thorsten Kleinjung, logarithme discret modulo un premier sûr de 530 bits^[24].
18 juin 2005, Antoine Joux et Reynald Lercier, logarithme discret modulo un premier sûr de 431 bits.

Voir aussi

Notes et références

Notes

↑ Aussi connu sous son nom anglais, generalised number field sieve, ou son acronyme : GNFS.
↑ Parfois appelé de manière moins précise « crible algébrique » ou « crible sur les corps de nombres », plus rarement « crible de corps de nombres ».
↑ Il existe un algorithme quantique asymptotiquement strictement plus efficace : l'algorithme de Shor. Cependant il n'est pas possible à l'heure actuelle d'exécuter cet algorithme pour de grands nombres.
↑ Lorsqu'on s'intéresse à des nombres de forme particulière, comme les nombres de Fermat ou de Mersenne, une version spécialisée de l'algorithme est plus efficace.
↑ Elle s'appuie notamment sur des hypothèses de répartition uniforme qui sont étayées par l'expérience mais pour lesquelles il n'y a pas de justification théorique.
↑ Il existe des algorithmes plus efficaces pour les corps finis de petite caractéristique, en particulier les corps binaires $\mathbb {F} _{2^{k}}$ , tels que le crible du corps de fonctions.
↑ Comme indiqué par (Lenstra 2017), ce découpage en deux phases a été identifié par Morrison et Brillhart dès 1975.
↑ Si la factorisation de $f$ n'est pas triviale on obtient directement une factorisation de $n$ .
↑ Dans le détail, si on note $\alpha _{1},\dotsc ,\alpha _{t}$ les conjugués complexes de $\alpha$ , alors ${\begin{aligned}N(a-b\alpha )&=\prod _{t=1}^{d}(a-b\alpha _{t})=b^{d}\prod _{t=1}^{d}\left({\frac {a}{b}}-\alpha _{t}\right)=b^{d}f\left({\frac {a}{b}}\right)\\&=a^{d}+c_{d-1}a^{d-1}b+\cdots +c_{1}ab^{d-1}+c_{0}b^{d}\end{aligned}}$ ce qui montre que la norme de $a-b\alpha$ est un polynôme en $a,b$ à coefficients entiers.
↑ La réciproque n'est en général pas vraie : par exemple on a dans $\mathbb {Z} [i]$ , donc $N((2+i)(2-i))=5^{2}$ est un carré, alors que $(2+i)(2-i)=5$ n'en est pas un.
↑ Voir (Lenstra 2017, Section 5.2.3).
↑ Voir (Lenstra 2017, Section 5.5.3).
↑ Voir (Lenstra 2017, Section 5.5.4).

Références

↑ (en) David Adrian, Karthikeyan Bhargavan, Zakir Durumeric et Pierrick Gaudry, « Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice », CCS '15 Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, ACM,‎ 12 octobre 2015, p. 5–17 (ISBN 9781450338325, DOI 10.1145/2810103.2813707, lire en ligne, consulté le 11 août 2018)
↑ (en) « The development of the number field sieve », Lecture Notes in Mathematics,‎ 1993 (ISSN 0075-8434 et 1617-9692, DOI 10.1007/bfb0091534, lire en ligne, consulté le 11 août 2018)
↑ (en) A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse et J. M. Pollard, « The number field sieve », STOC '90 Proceedings of the twenty-second annual ACM symposium on Theory of computing, ACM,‎ 1^er avril 1990, p. 564–572 (ISBN 0897913612, DOI 10.1145/100216.100295, lire en ligne, consulté le 11 août 2018)
↑ (en) A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse et J. M. Pollard, « The number field sieve », dans Lecture Notes in Mathematics, Springer Berlin Heidelberg, 1993 (ISBN 9783540570134, DOI 10.1007/bfb0091537, lire en ligne), p. 11–42
↑ (en) A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse et J. M. Pollard, « The factorization of the ninth Fermat number », Mathematics of Computation, vol. 61, n^o 203,‎ 1993, p. 319–349 (ISSN 0025-5718 et 1088-6842, DOI 10.1090/S0025-5718-1993-1182953-4, lire en ligne, consulté le 11 août 2018)
↑ (en) C. Pomerance, « A Tale of Two Sieves », Notices of the AMS,‎ décembre 1996, p. 1473–1485 (lire en ligne)
↑ (en) J. P. Buhler, H. W. Lenstra et Carl Pomerance, « Factoring integers with the number field sieve », dans Lecture Notes in Mathematics, Springer Berlin Heidelberg, 1993 (ISBN 9783540570134, DOI 10.1007/bfb0091539, lire en ligne), p. 50–94
↑ (en) Arjen K. Lenstra, chap. 5 « General purpose integer factoring », dans Joppe W. Bos et Arjen K. Lenstra, Topics in Computational Number Theory Inspired by Peter L. Montgomery, Cambridge University Press, 2017 (DOI 10.1017/9781316271575, lire en ligne)
↑ ^{a et b} (en) Antoine Joux et Reynald Lercier, « Number Field Sieve for DLP », dans Henk C. A. van Tilborg et Sushil Jajodia, Encyclopedia of Cryptography and Security, Boston, MA, Springer, 2011 (ISBN 978-1-4419-5905-8, lire en ligne), p. 867–873
↑ (en) Leonard M. Adleman, « The function field sieve », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, 1994 (ISBN 9783540586913, DOI 10.1007/3-540-58691-1_48, lire en ligne), p. 108–121
↑ (en) Michael A. Morrison et John Brillhart, « A method of factoring and the factorization of 𝐹₇ », Mathematics of Computation, vol. 29, n^o 129,‎ 1975, p. 183–205 (ISSN 0025-5718 et 1088-6842, DOI 10.1090/S0025-5718-1975-0371800-5, lire en ligne, consulté le 11 août 2018)
↑ (en) G. Villard, « A study of Coppersmith's block Wiedemann algorithm using matrix polynomials », LMC-IMAG, REPORT # 975 IM, vol. 38,‎ 1997 (lire en ligne, consulté le 11 août 2018)
↑ (en) G. Villard, « Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems (extended abstract) », ISSAC '97 Proceedings of the 1997 international symposium on Symbolic and algebraic computation, ACM,‎ 1^er juillet 1997, p. 32–39 (ISBN 0897918754, DOI 10.1145/258726.258742, lire en ligne, consulté le 11 août 2018)
↑ (en) N. de Bruijn, « On the number of positive integers $\leq x$ and free of prime factors $>y$ », Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen: Series A: Mathematical Sciences,‎ 1^er janvier 1966 (lire en ligne)
↑ (en) E. Canfield, P. Erdös et C. Pomerance, « On a problem of Oppenheim concerning “Factorisatio Numerorum” », Journal of Number Theory, vol. 17,‎ 1983, p. 1-28
↑ (en) Carl Pomerance, « Analysis and Comparison of Some Integer Factoring Algorithms », dans H. W. Lenstra et R. Tijdeman, Computational Methods in Number Theory, Math Centrum, Amsterdam, 1982, p. 89-139
↑ (en) Don Coppersmith, « Modifications to the Number Field Sieve », Journal of Cryptology, vol. 6, n^o 3,‎ 1993 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/bf00198464, lire en ligne, consulté le 11 août 2018)
↑ Maurice Kraitchik, Théorie des Nombres, Paris, Gauthier-Villars, 1922
↑ (en) Martin E. Hellman et Justin M. Reyneri, « Fast Computation of Discrete Logarithms in GF (q) », dans Advances in Cryptology, Springer US, 1983 (ISBN 9781475706048, DOI 10.1007/978-1-4757-0602-4_1, lire en ligne), p. 3–13
↑ ^{a et b} Emmanuel Thomé, “795-bit factoring and discrete logarithms,” December 2, 2019.
↑ (en) Thorsten Kleinjung, Kazumaro Aoki, Jens Franke et Arjen K. Lenstra, « Factorization of a 768-Bit RSA Modulus », dans Advances in Cryptology – CRYPTO 2010, Springer Berlin Heidelberg, 2010 (ISBN 9783642146220, DOI 10.1007/978-3-642-14623-7_18, lire en ligne), p. 333–350
↑ (en) Greg Childers, « Factorization of a 1061-bit number by the Special Number Field Sieve », IACR ePrint Archive, n^o 444,‎ 2012 (lire en ligne, consulté le 13 août 2018)
↑ (en) Thorsten Kleinjung, « Logarithme discret dans un cors de 768 bits », sur listserv.nodak.edu, 16 juin 2016 (consulté le 13 août 2018)
↑ (en) Thorsten Kleinjung, « Logarithme discret dans un corps de 530 bits », sur listserv.nodak.edu, 5 février 2007 (consulté le 13 août 2018)

[1] Aussi connu sous son nom anglais, generalised number field sieve, ou son acronyme : GNFS.

[2] Parfois appelé de manière moins précise « crible algébrique » ou « crible sur les corps de nombres », plus rarement « crible de corps de nombres ».

[3] Il existe un algorithme quantique asymptotiquement strictement plus efficace : l'algorithme de Shor. Cependant il n'est pas possible à l'heure actuelle d'exécuter cet algorithme pour de grands nombres.

[4] Lorsqu'on s'intéresse à des nombres de forme particulière, comme les nombres de Fermat ou de Mersenne, une version spécialisée de l'algorithme est plus efficace.

[5] Elle s'appuie notamment sur des hypothèses de répartition uniforme qui sont étayées par l'expérience mais pour lesquelles il n'y a pas de justification théorique.

[6] Il existe des algorithmes plus efficaces pour les corps finis de petite caractéristique, en particulier les corps binaires $\mathbb {F} _{2^{k}}$ , tels que le crible du corps de fonctions.

[17] Comme indiqué par (Lenstra 2017), ce découpage en deux phases a été identifié par Morrison et Brillhart dès 1975.

[21] Si la factorisation de $f$ n'est pas triviale on obtient directement une factorisation de $n$ .

[22] Dans le détail, si on note $\alpha _{1},\dotsc ,\alpha _{t}$ les conjugués complexes de $\alpha$ , alors ${\begin{aligned}N(a-b\alpha )&=\prod _{t=1}^{d}(a-b\alpha _{t})=b^{d}\prod _{t=1}^{d}\left({\frac {a}{b}}-\alpha _{t}\right)=b^{d}f\left({\frac {a}{b}}\right)\\&=a^{d}+c_{d-1}a^{d-1}b+\cdots +c_{1}ab^{d-1}+c_{0}b^{d}\end{aligned}}$ ce qui montre que la norme de $a-b\alpha$ est un polynôme en $a,b$ à coefficients entiers.

[23] La réciproque n'est en général pas vraie : par exemple on a dans $\mathbb {Z} [i]$ , donc $N((2+i)(2-i))=5^{2}$ est un carré, alors que $(2+i)(2-i)=5$ n'en est pas un.

[27] Voir (Lenstra 2017, Section 5.2.3).

[28] Voir (Lenstra 2017, Section 5.5.3).

[30] Voir (Lenstra 2017, Section 5.5.4).

[7] (en) David Adrian, Karthikeyan Bhargavan, Zakir Durumeric et Pierrick Gaudry, « Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice », CCS '15 Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, ACM,‎ 12 octobre 2015, p. 5–17 (ISBN 9781450338325, DOI 10.1145/2810103.2813707, lire en ligne, consulté le 11 août 2018)

[8] (en) « The development of the number field sieve », Lecture Notes in Mathematics,‎ 1993 (ISSN 0075-8434 et 1617-9692, DOI 10.1007/bfb0091534, lire en ligne, consulté le 11 août 2018)

[9] (en) A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse et J. M. Pollard, « The number field sieve », STOC '90 Proceedings of the twenty-second annual ACM symposium on Theory of computing, ACM,‎ 1^er avril 1990, p. 564–572 (ISBN 0897913612, DOI 10.1145/100216.100295, lire en ligne, consulté le 11 août 2018)

[10] (en) A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse et J. M. Pollard, « The number field sieve », dans Lecture Notes in Mathematics, Springer Berlin Heidelberg, 1993 (ISBN 9783540570134, DOI 10.1007/bfb0091537, lire en ligne), p. 11–42

[11] (en) A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse et J. M. Pollard, « The factorization of the ninth Fermat number », Mathematics of Computation, vol. 61, n^o 203,‎ 1993, p. 319–349 (ISSN 0025-5718 et 1088-6842, DOI 10.1090/S0025-5718-1993-1182953-4, lire en ligne, consulté le 11 août 2018)

[12] (en) C. Pomerance, « A Tale of Two Sieves », Notices of the AMS,‎ décembre 1996, p. 1473–1485 (lire en ligne)

[13] (en) J. P. Buhler, H. W. Lenstra et Carl Pomerance, « Factoring integers with the number field sieve », dans Lecture Notes in Mathematics, Springer Berlin Heidelberg, 1993 (ISBN 9783540570134, DOI 10.1007/bfb0091539, lire en ligne), p. 50–94

[14] (en) Arjen K. Lenstra, chap. 5 « General purpose integer factoring », dans Joppe W. Bos et Arjen K. Lenstra, Topics in Computational Number Theory Inspired by Peter L. Montgomery, Cambridge University Press, 2017 (DOI 10.1017/9781316271575, lire en ligne)

[:0-15] {a et b} (en) Antoine Joux et Reynald Lercier, « Number Field Sieve for DLP », dans Henk C. A. van Tilborg et Sushil Jajodia, Encyclopedia of Cryptography and Security, Boston, MA, Springer, 2011 (ISBN 978-1-4419-5905-8, lire en ligne), p. 867–873

[16] (en) Leonard M. Adleman, « The function field sieve », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, 1994 (ISBN 9783540586913, DOI 10.1007/3-540-58691-1_48, lire en ligne), p. 108–121

[18] (en) Michael A. Morrison et John Brillhart, « A method of factoring and the factorization of 𝐹₇ », Mathematics of Computation, vol. 29, n^o 129,‎ 1975, p. 183–205 (ISSN 0025-5718 et 1088-6842, DOI 10.1090/S0025-5718-1975-0371800-5, lire en ligne, consulté le 11 août 2018)

[19] (en) G. Villard, « A study of Coppersmith's block Wiedemann algorithm using matrix polynomials », LMC-IMAG, REPORT # 975 IM, vol. 38,‎ 1997 (lire en ligne, consulté le 11 août 2018)

[20] (en) G. Villard, « Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems (extended abstract) », ISSAC '97 Proceedings of the 1997 international symposium on Symbolic and algebraic computation, ACM,‎ 1^er juillet 1997, p. 32–39 (ISBN 0897918754, DOI 10.1145/258726.258742, lire en ligne, consulté le 11 août 2018)

[24] (en) N. de Bruijn, « On the number of positive integers $\leq x$ and free of prime factors $>y$ », Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen: Series A: Mathematical Sciences,‎ 1^er janvier 1966 (lire en ligne)

[25] (en) E. Canfield, P. Erdös et C. Pomerance, « On a problem of Oppenheim concerning “Factorisatio Numerorum” », Journal of Number Theory, vol. 17,‎ 1983, p. 1-28

[26] (en) Carl Pomerance, « Analysis and Comparison of Some Integer Factoring Algorithms », dans H. W. Lenstra et R. Tijdeman, Computational Methods in Number Theory, Math Centrum, Amsterdam, 1982, p. 89-139

[29] (en) Don Coppersmith, « Modifications to the Number Field Sieve », Journal of Cryptology, vol. 6, n^o 3,‎ 1993 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/bf00198464, lire en ligne, consulté le 11 août 2018)

[31] Maurice Kraitchik, Théorie des Nombres, Paris, Gauthier-Villars, 1922

[32] (en) Martin E. Hellman et Justin M. Reyneri, « Fast Computation of Discrete Logarithms in GF (q) », dans Advances in Cryptology, Springer US, 1983 (ISBN 9781475706048, DOI 10.1007/978-1-4757-0602-4_1, lire en ligne), p. 3–13

[d1-33] {a et b} Emmanuel Thomé, “795-bit factoring and discrete logarithms,” December 2, 2019.

[34] (en) Thorsten Kleinjung, Kazumaro Aoki, Jens Franke et Arjen K. Lenstra, « Factorization of a 768-Bit RSA Modulus », dans Advances in Cryptology – CRYPTO 2010, Springer Berlin Heidelberg, 2010 (ISBN 9783642146220, DOI 10.1007/978-3-642-14623-7_18, lire en ligne), p. 333–350

[35] (en) Greg Childers, « Factorization of a 1061-bit number by the Special Number Field Sieve », IACR ePrint Archive, n^o 444,‎ 2012 (lire en ligne, consulté le 13 août 2018)

[36] (en) Thorsten Kleinjung, « Logarithme discret dans un cors de 768 bits », sur listserv.nodak.edu, 16 juin 2016 (consulté le 13 août 2018)

[37] (en) Thorsten Kleinjung, « Logarithme discret dans un corps de 530 bits », sur listserv.nodak.edu, 5 février 2007 (consulté le 13 août 2018)

[Note 1]

[Note 2]

[Note 3]

[Note 4]

[Note 5]

[Note 6]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[Note 7]

[11]

[12]

[13]

[Note 8]

[Note 9]

[Note 10]

[14]

[15]

[16]

[Note 11]

[Note 12]

[17]

[Note 13]

[18]

[19]

[20]

[21]

[22]

[23]

[24]