Quadratic Sieve
Le crible quadratique cherche x tel que x^2≡y^2 (mod n), de sorte que pgcd(x±y,n) puisse révéler un facteur ; c'est la méthode de factorisation la plus rapide en dessous de 100 chiffres.
Objectif
Factoriser des entiers de taille moyenne (~100 chiffres) aussi vite que possible.
Mécanisme
On cherche de nombreux x_i tels que x_i^2 mod n soit B-friable, puis on utilise l'algèbre linéaire sur GF(2) pour les combiner afin que le produit des carrés soit un carré parfait. La combinaison donne X^2≡Y^2 (mod n), et pgcd(X±Y,n) peut être non trivial.
Cas d’usage
- Factorisation d'entiers
- Cryptanalyse
- Algorithmes de théorie des nombres