Quadratic Sieve
La criba cuadrática busca x con x^2≡y^2 (mod n), de modo que gcd(x±y,n) puede revelar un factor; es el método de factorización más rápido por debajo de 100 dígitos.
Propósito
Factorizar enteros de tamaño medio (~100 dígitos) lo más rápido posible.
Mecanismo
Se buscan muchos x_i tales que x_i^2 mod n sea B-suave, y se usa álgebra lineal sobre GF(2) para combinarlos de modo que el producto de cuadrados sea un cuadrado perfecto. La combinación da X^2≡Y^2 (mod n), y gcd(X±Y,n) puede ser no trivial.
Casos de uso
- Factorización de enteros
- Criptoanálisis
- Algoritmos de teoría de números