Crible quadratique

L'algorithme du crible quadratique est un algorithme de factorisation fondé sur l'arithmétique modulaire. C'est en pratique le plus rapide après le crible général des corps de nombres, lequel est cependant bien plus compliqué, et n'est plus performant que pour factoriser un nombre entier d'au moins cent chiffres. Le crible quadratique est un algorithme de factorisation non spécialisé, c'est-à-dire que son temps d'exécution dépend uniquement de la taille de l'entier à factoriser, et non de propriétés particulières de celui-ci.

Objectif de base

L'algorithme, mis au point en 1981 par Carl Pomerance, est un raffinement de la méthode de factorisation de Dixon, elle-même basée sur celle de Fermat : on essaye d'établir une congruence de carrés modulo n (l'entier à factoriser), qui, souvent, conduit bien à une factorisation de n.

L'algorithme fonctionne en deux phases :

la phase de collecte des données, où il collecte les informations qui peuvent conduire à une congruence de carrés, et
la phase d'exploitation des données, où il place toutes les données qu'il a collectées dans une matrice et la résout pour obtenir une congruence de carrés.

La phase de collecte peut se paralléliser facilement et efficacement, mais pas la phase d'exploitation, à moins d'avoir peu de sous-systèmes et que chacun d'eux dispose d'une mémoire suffisante pour stocker toute la matrice (dans ce cas on peut utiliser l'algorithme par blocs de Wiedemann (en)).

L'approche naïve pour trouver une congruence de carrés est de choisir un nombre au hasard, l'élever au carré, et espérer que le plus petit reste (positif ou nul) modulo n soit un carré parfait (i.e. soit le carré d'un entier). Par exemple, modulo 5959, l'entier 80² est congru à 441=21². Pour n grand, cette approche trouve rarement une congruence de carrés, mais lorsque cela arrive, cette congruence est le plus souvent non triviale donc permet de factoriser n.

La durée d'exécution[1] du crible quadratique pour factoriser un entier n est en

O\left(e^{\sqrt {\log n\log \log n}}\right)=L_{n}\left[1/2,1\right]

avec la notation O de Landau et la notation L.

Optimisation de la recherche de congruences

Le crible quadratique essaie de trouver des couples d'entiers x et y(x) (où y(x) est une fonction de x) satisfaisant une condition bien plus faible que x² ≡ y² (mod n). Il choisit un ensemble de nombres premiers qu'on appelle base de facteurs, et cherche des x pour lesquels le « plus petit reste absolu » y(x) de x² modulo n se factorise complètement sur cette "base". De tels couples d'entiers sont dits réguliers relativement à cette base, et la factorisation de y(x) sur la base, jointe à la valeur de x, constitue ce qu'on appelle une relation. Le crible quadratique accélère le processus de recherche de relations en prenant x proche de la racine carrée de n. Ainsi y(x) sera plus petit, et aura donc plus de chance d'être « régulier ». Pour x=[√n]+z avec z entier "petit",

y(x)=x^{2}-n=\left(\left\lfloor {\sqrt {n}}\right\rfloor +z\right)^{2}-n\approx 2z\left\lfloor {\sqrt {n}}\right\rfloor \ .

Néanmoins, cela implique aussi que y croît linéairement avec z.

Une autre façon d'augmenter les chances de régularité est d'augmenter simplement la taille de la base, mais cela impose de collecter plus de relations. En effet, pour être sûr que les relations sont linéairement dépendantes, il faut qu'il y en ait au moins une de plus que le nombre de facteurs premiers dans la base.

Relations partielles et cycles

Même si, dans une relation, y(x) n'est pas régulier, il peut arriver qu'en fusionnant deux telles relations partielles on en forme une "complète". Il faut pour cela qu'en dehors de la base, les facteurs premiers des deux y soient les mêmes. Par exemple, si la base est {2, 3, 5, 7} et n = 91, en faisant le produit des deux relations partielles

21^{2}\equiv 7^{1}\cdot 11{\pmod {91}}

et

29^{2}\equiv 2^{1}\cdot 11{\pmod {91}}

on obtient

(21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}\cdot 11^{2}{\pmod {91}}~.

On en déduit une relation complète en multipliant les deux côtés par le carré de 11^-1 modulo 91, c'est-à-dire de 58 (valeur obtenue à l'aide de l'algorithme d'Euclide étendu, par exemple) :

(58\cdot 21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}~,

soit

14^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}~.

Une telle relation complète (obtenue par combinaison de relations partielles) est appelée un cycle. Quelquefois, la formation d'un cycle à partir de deux relations partielles conduit directement à une congruence de carrés, mais rarement.

Vérifier la régularité par criblage

Il existe plusieurs manières de vérifier la régularité des y. La plus évidente est la méthode des essais de divisions, bien que ceci augmente le temps d'exécution pour la phase de collecte des données. Une autre méthode parfois utilisée est la méthode des courbes elliptiques. Mais la pratique la plus courante est de procéder par criblage.

y(x)=x^{2}-n\,\!

y(x+kp)=(x+kp)^{2}-n\,\!

y(x+kp)=x^{2}+2xkp+(kp)^{2}-n\,\!

y(x+kp)=y(x)+2xkp+(kp)^{2}\equiv y(x){\pmod {p}}

Ainsi, si l'on connait un x tel que y(x) ≡ 0 (mod p), on en déduit toute une suite de y qui sont divisibles par p. En répétant ce processus pour d'autres valeurs de p, on trouve des valeurs régulières, par un processus de criblage (analogue au crible d'Ératosthène) au lieu d'avoir à tester la régularité à chaque fois (ce test systématique prendrait trop de temps pour de grands nombres comme ceux des records de factorisation ci-dessous). Au cours de ce processus on perd l'information détaillée de la factorisation des y réguliers collectés, mais comme ils n'ont que de "petits" facteurs (ceux de la base), on peut la recalculer rapidement.

Polynômes multiples

Dans la pratique, le seul polynôme y(x) = x² − n ne fournit pas suffisamment de (x, y) réguliers sur la base des facteurs. On utilise alors toute une famille de polynômes qui, pour être des carrés modulo n, doivent être d'une forme similaire à l'original :

y(x)=(Ax+B)^{2}-n\qquad A,B\in \mathbb {Z} ~.

Cette approche, appelée crible quadratique à polynômes multiples (MPQS, pour Multiple Polynomial Quadratic Sieve), est parfaitement adaptée à la parallélisation.

Exemple

Voici un exemple. Soit n = 1817. La partie entière de sa racine carrée est 42. Comme n est petit, le polynôme y(z) = (42+z)²-1817 suffit (pas besoin du crible multipolynomial).

Collecte des données

On se limite, comme base F de facteurs, à -1 et aux nombres premiers p pour lesquels n est un résidu quadratique modulo p :

F=\lbrace -1,2,7,13\rbrace .

Puisque F compte 4 éléments, on a besoin de 5 couples réguliers (z, y(z)). Les premiers trouvés (par ordre croissant sur z) sont les suivants :

z	y(z)=(42+z)²-1817	factorisation de y(z)
1	32	−1⁰ • 2⁵ • 7⁰ • 13⁰
3	208	−1⁰ • 2⁴ • 7⁰ • 13¹
9	784	−1⁰ • 2⁴ • 7² • 13⁰
81	13312	−1⁰ • 2¹⁰ • 7⁰ • 13¹
103	19208	−1⁰ • 2³ • 7⁴ • 13⁰

(on pourrait aussi choisir des z négatifs).

Exploitation des données

On forme la matrice des exposants qui interviennent dans la factorisation des y(z) :

{\begin{pmatrix}0&5&0&0\\0&4&0&1\\0&4&2&0\\0&10&0&1\\0&3&4&0\\\end{pmatrix}}\equiv {\begin{pmatrix}0&1&0&0\\0&0&0&1\\0&0&0&0\\0&0&0&1\\0&1&0&0\\\end{pmatrix}}{\pmod {2}}

La troisième ligne (qui correspond à (z, y) = (9, 784)) est nulle modulo 2 donc est déjà une congruence de carrés, qu'on peut utiliser pour factoriser n : modulo 1817,

51^{2}=(42+9)^{2}\equiv y(9)=2^{4}.7^{2}=(2^{2}.7)^{2}=28^{2}~,

et pgcd(51+28,1817) = 79, pgcd(51-28,1817) = 23. Ce sont les deux facteurs non triviaux de 1817.

On aurait pu utiliser d'autres congruences de carrés déduites de cette matrice. Par exemple en combinant la deuxième ligne et la quatrième (puisque leur somme est paire) :

(5535)^{2}=45^{2}.123^{2}=(42+3)^{2}(42+81)^{2}\equiv y(3)y(81)=2^{14}.13^{2}=(2^{7}.13)^{2}=1664^{2}~,

et pgcd(5535+1664,1817)=23, pgcd(5535-1664,1817)=79.

Cet exemple montre aussi que le crible quadratique n'est utile que pour n grand. Pour un nombre aussi petit que 1817, cet algorithme est un canon pour tuer une mouche. Les essais de divisions pourraient trouver un facteur en 9 divisions.

Records de factorisation

Jusqu'à la découverte du crible généralisé sur les corps de nombres, l'algorithme non spécialisé le plus rapide (asymptotiquement) que l'on connaissait était le crible quadratique. À présent, la méthode des courbes elliptiques possède le même temps d'exécution asymptotique que le crible quadratique (dans le cas où n est produit de deux grands nombres premiers), mais dans la pratique, le crible quadratique est plus rapide car il utilise des calculs en simple précision au lieu des calculs en multi-précision pour la méthode des courbes elliptiques.

Le 2 avril 1994, la factorisation de RSA-129 fut achevée à l'aide du crible quadratique. C'est un nombre de 129 chiffres, produit de deux grands nombres premiers, l'un de 64 chiffres et l'autre de 65. La base des facteurs pour cette factorisation contenait 524 339 nombres premiers. La collecte des données prit 5 000 années MIPS faite par calcul distribué via Internet. Les données collectées totalisèrent 2 Go. La phase d'exploitation des données prit 45 heures sur le supercalculateur MasPar (en) (massivement parallèle) de Bellcore (devenu depuis Telcordia Technologies (en)). Ce fut, parmi les records publiés, le plus grand nombre factorisé par un algorithme non spécialisé, jusqu'à ce que le crible sur les corps de nombres soit utilisé pour la factorisation de RSA-130, terminée le 10 avril 1996. Tous les nombres RSA factorisés depuis l'ont été par le crible sur les corps de nombres.

Le record suivant du crible quadratique est la décomposition, en 2001, d'un nombre de 135 chiffres en produit de deux facteurs premiers, l'un de 66 chiffres et l'autre de 69. (Ce produit est un diviseur du nombre $2^{803}-2^{402}+1$ , qui est lui-même un facteur aurifeuillien (en) de $2^{1606}+1$ .)

Notes et références

(en) Carl Pomerance, « A Tale of Two Sieves », Notices of the AMS, vol. 43, n^o 12,‎ décembre 1996, p. 1473–1485 (lire en ligne)

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Quadratic sieve » (voir la liste des auteurs).

Article lié

Factorisation par fraction continue

Portail de l'informatique théorique
Arithmétique et théorie des nombres

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] (en) Carl Pomerance, « A Tale of Two Sieves », Notices of the AMS, vol. 43, n^o 12,‎ décembre 1996, p. 1473–1485 (lire en ligne)