tamiz de campo de número general

Se eligen dos polinomios f ( x ) y g ( x ) de grados pequeños d y e , que tienen coeficientes enteros, que son irreducibles sobre los racionales y que, cuando se interpretan módulo n , tienen una raíz entera común m . No se conoce una estrategia óptima para elegir estos polinomios; un método simple es obtener f a partir de la expansión en base m de n para una elección apropiada de m . Más precisamente: para cualquier elección de m , escribir n en base m es, por definición, encontrar dígitos${\textstyle a_{0},a_{1},\ldots ,a_{d}}$dónde${\textstyle 0\leq a_{i}<m}$para cada i , tal que

${\displaystyle n=a_{d}m^{d}+\cdots +a_{1}m+a_{0}}$,

lo que a su vez significa que m es una raíz del polinomio${\textstyle f(x)=a_{d}x^{d}+\cdots +a_{1}x+a_{0}}$módulo n . Para los propósitos del cribado general de cuerpos numéricos, primero fijamos un grado apropiado d y luego realizamos la expansión anterior para una serie de valores m de orden n ^{1/ d} , después de lo cual elegimos el polinomio f como aquel cuyos coeficientes son en conjunto los más pequeños entre los candidatos obtenidos de esta manera. Luego simplemente establecemos${\textstyle g(x)=xm}$.

_{Consideremos los anillos de} cuerpos numéricos Z [ r₁ _] y Z [ r₂ _] , donde r₁ y _r₂ son raíces de los polinomios f y g . Dado que f es de grado d con coeficientes enteros, si a y b son enteros, también lo será b ^d · f ( a / b ), que llamamos r . De manera similar, s = b ^e · g ( a / b ) es un entero. El objetivo es encontrar valores enteros de a y b que simultáneamente hagan que r y s sean suaves con respecto a la base de primos elegida. Si a y b son pequeños, entonces r y s también lo serán, aproximadamente del tamaño de m , y tenemos una mayor probabilidad de que sean suaves al mismo tiempo. El enfoque más conocido actualmente para esta búsqueda es el cribado reticular ; para obtener rendimientos aceptables, es necesario utilizar una base de factores grande. Estos pares también se denominan "relaciones". ^{[ 6 ]}

Con suficientes pares de este tipo, mediante la eliminación gaussiana , se pueden obtener productos de ciertos r y de los correspondientes s que sean cuadrados simultáneamente. Se requiere una condición ligeramente más estricta: que sean normas de cuadrados en nuestros cuerpos numéricos, pero esta condición también se puede lograr con este método. Cada r es una norma de a  − r ₁ b y, por lo tanto, el producto de los factores correspondientes a − r ₁ b es un cuadrado en Z [ r ₁ ], con una "raíz cuadrada" que se puede determinar (como producto de factores conocidos en Z [ r ₁ ]); normalmente se representará como un número algebraico irracional . De manera similar, el producto de los factores a − r ₂ b es un cuadrado en Z [ r ₂ ], con una "raíz cuadrada" que también se puede calcular. Cabe señalar que el uso de la eliminación gaussiana no proporciona el tiempo de ejecución óptimo del algoritmo. En su lugar, se utilizan algoritmos de resolución de matrices dispersas como Block Lanczos o Block Wiedemann .     

Dado que m es una raíz tanto de f como de g mod n , existen homomorfismos de los anillos Z [ r ₁ ] y Z [ r ₂ ] al anillo Z / n Z (los enteros módulo n ), que mapean r ₁ y r ₂ a m , y estos homomorfismos mapearán cada "raíz cuadrada" (típicamente no representada como un número racional) a su representante entero. Ahora bien, el producto de los factores a  − mb mod n se puede obtener como un cuadrado de dos maneras, una para cada homomorfismo. Así, se pueden encontrar dos números x e y , con x ² − y ² divisible por n y nuevamente con una probabilidad de al menos un medio obtenemos un factor de n al encontrar el máximo común divisor de n y x − y .     

El paso de posprocesamiento implica grandes cantidades de datos generados a partir de los dos pasos anteriores. Prácticamente se realiza dividiéndolo en tres fases: ^{[ 6 ]}

1. El filtrado consiste en examinar las relaciones para encontrar una colección suficiente para construir una matriz. Este paso puede fallar si no se proporcionan suficientes relaciones, y es difícil estimar de antemano cuántas se necesitan. Utilizar más relaciones de las necesarias suele facilitar los pasos posteriores, ya que produce una matriz más pequeña.
2. El álgebra lineal busca un grupo de vectores que se encuentren en el espacio nulo de la matriz muy grande producida en el paso anterior.
3. Raíz cuadrada, que se puede calcular sobre cualquier solución del paso anterior.

GNFS implica grandes cantidades de computación y requiere alguna forma de computación distribuida para completarse en plazos prácticos dados los grandes números como RSA-768 . Los siguientes pasos se pueden realizar en paralelo: ^{[ 7 ]}

• El tamizado, que podría producir relaciones duplicadas y requiere grandes cantidades de computación.
• Eliminación de relaciones duplicadas y eliminación de relaciones únicas.
• El álgebra lineal, que requiere enormes cantidades de cálculos.

La prueba de caracteres cuadráticos se puede aplicar a los resultados de la resolución de matrices para identificar soluciones verdaderas. En el caso de RSA-768, 460 de 512 fueron verdaderas. Ocho de ellas fueron seleccionadas para el paso cuadrado, lo que produjo 5 factorizaciones idénticas en el paso final después de una cantidad relativamente pequeña de cálculos. ^{[ 7 ]}

Una descripción más detallada de un esfuerzo distribuido se puede encontrar en RSA-240, DLP-240 y RSA-250, utilizando el software CADO-NFS. Los archivos de reproducción completos se proporcionan en un repositorio enlazado desde el apéndice del artículo. ^{[ 8 ]}

Un proyecto llamado NFSNET se desarrolló desde 2002 ^{[ 9 ]} hasta al menos 2007. Utilizaba computación distribuida voluntaria en Internet . ^{[ 10 ]} Paul Leyland del Reino Unido y Richard Wackerbarth de Texas participaron. ^{[ 11 ]}

Un intento más reciente, denominado NFS@Home , sigue en funcionamiento a fecha de septiembre de 2025. Históricamente, ha utilizado versiones modificadas de msieve. Generalmente, emplea filtros de campo numérico especiales.