Crible quadratique

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

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

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

on obtient

${\displaystyle (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) :

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

${\displaystyle 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.

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.

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

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

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

${\displaystyle 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.

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

${\displaystyle 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 :

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

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

${\displaystyle {\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,

${\displaystyle 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) :

${\displaystyle (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.