##  [Criba Cuadrática](/es/node/61996) 

 Definición

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

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

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

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

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

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

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

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

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.