Number Field Sieve
Le crible algébrique est l'algorithme classique de factorisation le plus rapide connu ; il construit des congruences de carrés via des corps de nombres algébriques avec une complexité sous-exponentielle.
Objectif
Factoriser les grands entiers (>100 chiffres) au plus vite, en définissant la frontière de sécurité de RSA.
Mécanisme
On choisit un polynôme f et un entier m tels que f(m)≡0 (mod n), puis on cherche des éléments friables dans le corps de nombres Q(α). L'algèbre linéaire les combine pour que les normes deviennent des carrés, produisant x^2≡y^2 (mod n). Complexité L_n[1/3, (64/9)^(1/3)].
Cas d’usage
- Analyse de la sécurité de RSA
- Factorisation de grands entiers
- Applications cryptographiques