Algoritmo de factorización de propósito general que busca congruencias de cuadrados módulo n recogiendo muchos valores que se factoricen completamente sobre una base de factores elegida y combinándolos mediante álgebra lineal para producir un cuadrado módulo n.

Principio

Encontrar enteros x tales que x^2 mod n sea B-liso (es decir, se factorice completamente sobre una base de factores); registrar vectores de exponentes módulo 2 para estas relaciones y resolver un sistema lineal para obtener un subconjunto cuyo producto dé una congruencia de cuadrados, luego calcular un gcd para extraer factores.

Demostración

Para un n moderado, elegir una base de factores de primos pequeños, cribar valores de x en torno a sqrt(n) para hallar x^2 - n B-lisos, recopilar suficientes relaciones, calcular un vector del núcleo módulo 2, multiplicar las relaciones correspondientes para obtener y^2 ≡ z^2 (mod n) y entonces gcd(|y-z|, n) puede producir un factor no trivial.

Aplicación incorrecta

Elegir una base de factores inadecuada o no recoger suficientes relaciones lisas, o aplicar la criba cuadrática a tamaños donde la criba de cuerpos de números (NFS) es asintóticamente superior sin justificación.

Consecuencia

Muy eficaz para números de tamaño intermedio: significativamente más rápido que la división por ensayo y Rho de Pollard para semiprimos grandes hasta cierto umbral; requiere memoria y álgebra lineal considerables pero es práctico y paralelizable.

Inversión

En lugar de cribar un polinomio cuadrático sobre los enteros, usar cuerpos numéricos algebraicos para producir normas más lisas y relaciones (como en NFS) para llevar mucho más lejos el límite práctico.

Límite

Criba de propósito general adecuada para enteros medianos a grandes pero superada asintóticamente por NFS para entradas muy grandes; supone la posibilidad de encontrar muchos valores B-lisos y excluye algoritmos especializados adaptados a estructuras concretas.

Tensión semántica

Compite con la criba de cuerpos de números: ambas recogen relaciones y resuelven sistemas lineales, pero QS opera con polinomios cuadráticos y bases de factores enteras mientras NFS explota cuerpos de números algebraicos para un mejor comportamiento asintótico.

Síntesis

La criba cuadrática convierte la factorización en la búsqueda de muchos residuos cuadráticos lisos, usando cribado y álgebra lineal para combinar relaciones en una congruencia de cuadrados que produce factores no triviales mediante gcd.