El algoritmo de factorización clásico con el mejor comportamiento asintótico conocido para enteros muy grandes, que utiliza cuerpos numéricos algebraicos, selección de polinomios, cribado de normas y álgebra lineal a gran escala para producir relaciones que conducen a congruencias de cuadrados módulo n.

Principio

Seleccionar polinomios que definan cuerpos numéricos y mapeos a Z/nZ, cribar en dos dominios para coleccionar relaciones donde las normas algebraicas son lisas sobre bases de factores elegidas, ensamblar muchas relaciones en una matriz dispersa y resolver módulo 2 para combinar en congruencias de cuadrados cuyos gcd con n dan factores no triviales.

Demostración

Para un semiprimo grande n, escoger un par de polinomios y una base de factores, cribar para encontrar normas lisas en los lados algebraico y racional, reunir suficientes relaciones, ejecutar una rutina de álgebra lineal dispersa para hallar dependencias, formar congruencias de cuadrados y calcular gcd para extraer factores.

Aplicación incorrecta

Intentar aplicar NFS a enteros pequeños donde la selección de polinomios y el coste del álgebra lineal hacen que sea más lento que métodos más sencillos, o escoger polinomios pobres que destruyan el rendimiento práctico.

Consecuencia

Proporciona el mejor rendimiento práctico conocido para factorizar enteros muy grandes (cientos de dígitos) en hardware clásico; sin embargo exige recursos computacionales considerables, implementaciones sofisticadas y un ajuste cuidadoso.

Inversión

Contrastar con cribas elementales o cuadráticas que permanecen prácticas en tamaños menores; o con algoritmos cuánticos (Shor) que superarán asintóticamente a todos los cribados clásicos si se dispusiera de ordenadores cuánticos tolerantes a fallos a gran escala.

Límite

Asintóticamente óptimo entre los algoritmos clásicos conocidos para enteros enormes pero impráctico para entradas pequeñas por el coste de preparación; excluye algoritmos cuánticos de factorización y métodos algebraicos especializados para formas concretas salvo adaptaciones.

Tensión semántica

Compite con la criba cuadrática en rangos prácticos y con métodos especializados para ciertos enteros de forma particular; conceptualmente se distingue por explotar cuerpos numéricos y el cribado de normas en lugar de limitarse a residuos cuadráticos enteros.

Síntesis

La criba de cuerpos de números reduce la factorización a la búsqueda de muchas normas algebraicas lisas en cuerpos numéricos, combinando cribado y álgebra lineal a gran escala para convertir esas relaciones en congruencias de cuadrados que producen factores, alcanzando el mejor tiempo asintótico clásico conocido para enteros muy grandes.