Crible quadratique

Prenons un entier dont on cherche les facteurs. Autour de sa racine carrée, on élève plusieurs nombres au carré, puis on regarde l’écart avec l’entier de départ. Certains écarts se décomposent seulement en petits nombres premiers : ce sont des nombres lisses.

Le crible repère rapidement ces écarts favorables. Il en combine ensuite assez pour fabriquer deux carrés qui ont le même reste dans une division par l’entier étudié. La différence entre leurs racines révèle souvent un facteur caché.

Le crible quadratique est un algorithme qui factorise un entier composé N. Il construit des valeurs d’un polynôme quadratique, typiquement des différences entre un carré proche et N, puis cherche celles qui se décomposent entièrement sur une base de petits nombres premiers. Une telle valeur est dite lisse relativement à cette base. Le criblage sert à repérer ces valeurs sans tester séparément toutes les divisions possibles.

Pour chaque valeur lisse, l’algorithme enregistre la parité des exposants de ses facteurs premiers, en intégrant aussi le signe comme facteur −1. Une dépendance entre ces vecteurs de parités sélectionne alors un produit positif dans lequel tous les exposants sont pairs. Ce produit est donc un carré. On obtient alors deux entiers X et Y tels que $X^2\equiv Y^2(\mathrm{m}\mathrm{o}\mathrm{d}N)X^2\; \backslash equiv\; Y^2\; \backslash pmod\; N$. Si X n’est congru ni à Y ni à son opposé modulo N, les nombres PGCD(X − Y, N) et PGCD(X + Y, N) donnent des facteurs non triviaux de N.

Dans les analyses heuristiques usuelles, la méthode a une complexité attendue sub-exponentielle. Elle reste adaptée aux entiers de taille moyenne, tandis que le crible du corps de nombres a pris l’avantage pour les très grands entiers.

Factorisons N = 187 avec la base de facteurs {2, 3, 19}. Deux valeurs du polynôme Q(x) = x² − 187 ont été retenues par le criblage : x = 15 et x = 23.

1. Pour x = 15, Q(15) = 15² − 187 = 38 = 2 × 19.
2. Pour x = 23, Q(23) = 23² − 187 = 342 = 2 × 3² × 19.

3. Le produit des deux valeurs est un carré : $38\times 342=2^2\times 3^2\times {19}^2={114}^{2}38\; \backslash times\; 342\; =\; 2^2\; \backslash times\; 3^2\; \backslash times\; 19^2\; =\; 114^2$.
4. Le produit des deux abscisses vaut 15 × 23 = 345, soit 158 modulo 187. Nous avons donc 158² ≡ 114² modulo 187.

5. Les deux PGCD séparent les facteurs : PGCD(158 − 114, 187) = PGCD(44, 187) = 11, et PGCD(158 + 114, 187) = PGCD(272, 187) = 17. La figure synthétise l’enchaînement des deux relations lisses jusqu’aux facteurs.

Le contrôle est direct : 11 × 17 = 187. Les deux facteurs sont non triviaux, car ils sont strictement compris entre 1 et 187.

Pour factoriser un entier de taille moyenne sans petit diviseur évident, on choisit une base de facteurs, on crible les valeurs d’un polynôme quadratique, puis on conserve les valeurs lisses. Le calcul linéaire sur les parités indique ensuite quelles relations multiplier.

Avant ce travail, les divisions par de petits nombres premiers éliminent les cas immédiats. Si l’entier est très grand, le crible du corps de nombres devient préférable ; le critère observable est alors la taille de l’entier et le coût estimé de la collecte des relations.

Dans une implémentation, l’essentiel consiste à équilibrer la taille de la base et la zone criblée. Une base plus large rend davantage de valeurs lisses, mais augmente le nombre de relations nécessaires et le coût de l’algèbre linéaire.

Crible d’Ératosthène. Il énumère les nombres premiers jusqu’à une borne en rayant leurs multiples. Le crible quadratique, lui, cherche des relations lisses pour factoriser un entier donné ; factoriser 187 relève du second problème.

Méthode de Fermat. Elle cherche directement une écriture de N comme différence de deux carrés. Le crible quadratique accepte plusieurs valeurs lisses et les combine ; dans l’exemple de 187, deux relations distinctes produisent le carré 114².

Crible du corps de nombres. Les deux méthodes sont sub-exponentielles et exploitent des relations lisses, mais leurs polynômes et leurs cadres algébriques diffèrent. Pour de très grands entiers, le crible du corps de nombres est le choix le plus efficace.

Relation triviale. Une congruence de carrés ne suffit pas toujours. Si X ≡ Y ou X ≡ −Y modulo N, les PGCD rendent 1 et N au lieu de deux facteurs utiles ; il faut alors combiner une autre dépendance.

Relations insuffisantes. Avec une base contenant k nombres premiers, il faut en pratique collecter plus de k relations pour espérer une dépendance exploitable entre les vecteurs de parités. Si le calcul linéaire n’en trouve pas, le criblage doit continuer.

Mauvais réglage de la base. Une base trop petite fournit peu de valeurs lisses ; une base trop grande alourdit la collecte et l’algèbre linéaire. Le symptôme est un temps dominé par l’une de ces deux phases, et le remède consiste à ajuster ensemble la base et l’intervalle de criblage.

Prétraitement oublié. Un entier pair, une puissance parfaite ou un entier ayant un petit facteur ne justifie pas d’emblée le crible complet. Ces cas se détectent d’abord par des tests plus directs, puis le crible traite la partie composée restante si nécessaire.

La fiche Factorisation replace le résultat 187 = 11 × 17 dans le vocabulaire général des produits et des facteurs.

La fiche congruence modulo n précise le langage employé lorsque 158² et 114² ont le même reste modulo 187.

L’article La factorisation des grands entiers : élargit la perspective aux stratégies conçues pour des nombres bien plus difficiles à décomposer.

La fiche Corps de nombres ouvre sur le cadre algébrique qui distingue le crible du corps de nombres du crible quadratique.