Méthode de factorisation générale qui recherche des congruences de carrés modulo n en rassemblant de nombreuses valeurs qui se factorisent complètement sur une base de facteurs choisie et en les combinant par algèbre linéaire pour produire un carré modulo n.

Principe

Trouver des entiers x tels que x^2 mod n soit B-lisse (c'est-à-dire entièrement factorisable sur une base de petits premiers) ; enregistrer les vecteurs d'exposants modulo 2 de ces relations et résoudre un système linéaire pour obtenir un sous-ensemble dont le produit donne une congruence de carrés, puis calculer un gcd pour extraire des facteurs.

Démonstration

Pour un n modéré, choisir une base de facteurs de petits premiers, cribler des valeurs x autour de sqrt(n) pour trouver des x^2 - n B-lisses, rassembler suffisamment de relations, calculer un vecteur du noyau modulo 2, multiplier les relations correspondantes pour obtenir y^2 ≡ z^2 (mod n) puis gcd(|y-z|, n) peut produire un facteur non trivial.

Mauvaise application

Choisir une base de facteurs inadéquate ou ne pas collecter assez de relations lisses, ou appliquer le crible quadratique à des tailles pour lesquelles le crible du corps de nombres est asymptotiquement supérieur sans justification.

Conséquence

Très efficace pour des nombres de tailles intermédiaires : nettement plus rapide que la division d'essai et Rho de Pollard pour des semiprimes importants jusqu'à un certain seuil ; demande une mémoire et de l'algèbre linéaire substantielles mais reste pratique et parallélisable.

Inversion

Au lieu de cribler un polynôme quadratique sur les entiers, utiliser des corps de nombres algébriques pour produire des normes plus lisses et des relations (comme dans le crible du corps de nombres) afin d'étendre la limite pratique beaucoup plus loin.

Limite

Crible général adapté aux entiers moyens à grands mais dépassé asymptotiquement par le crible du corps de nombres pour des tailles très importantes ; suppose la possibilité de trouver de nombreuses valeurs B-lisses et exclut les algorithmes spécialisés adaptés à une structure particulière.

Tension sémantique

Concurrence avec le crible du corps de nombres : tous deux collectent des relations et résolvent des systèmes linéaires, mais le crible quadratique opère sur des polynômes quadratiques et des bases de facteurs entières tandis que NFS exploite des corps de nombres algébriques pour un meilleur comportement asymptotique.

Synthèse

Le crible quadratique transforme la factorisation en la recherche de nombreuses résidus quadratiques lisses, utilisant criblage et algèbre linéaire pour combiner les relations en une congruence de carrés qui fournit des facteurs non triviaux via le gcd.