Tamiz de campo de números generales

En teoría de números , el tamiz de campo numérico general ( GNFS ) es el algoritmo clásico más eficiente conocido para factorizar números enteros mayores que $10$ $100$ . Heurísticamente , su complejidad para factorizar un número entero $n$ (que consta de $⌊log$ $2$ $n$ $⌋ + 1$ bits) es de la forma

{\begin{aligned}&\exp \left(\left((64/9)^{1/3}+o(1)\right)\left(\log n\right)^{1/ 3}\left(\log \log n\right)^{2/3}\right)\\[5pt]={}&L_{n}\left[1/3,(64/9)^{1/ 3}\right]\end{aligned}}

en notaciones O y L. ^[1] Es una generalización del tamiz de campos numéricos especiales : mientras que este último solo puede factorizar números de una determinada forma especial, el tamiz de campos numéricos general puede factorizar cualquier número excepto los poderes primos (que son triviales de factorizar tomando raíces) .

El principio de la criba de campos numéricos (tanto especial como general) puede entenderse como una mejora de la criba racional más simple o la criba cuadrática . Cuando se utilizan tales algoritmos para factorizar un número grande $n$ , es necesario buscar números suaves (es decir, números con factores primos pequeños) de orden $n 1/2$ . El tamaño de estos valores es exponencial en el tamaño de $n$ (ver más abajo). El tamiz de campo numérico general, por otro lado, logra buscar números suaves que sean subexponenciales en el tamaño de $n$ . Dado que estos números son más pequeños, es más probable que sean fluidos que los números inspeccionados en algoritmos anteriores. Ésta es la clave de la eficacia del tamiz de campos numéricos. Para lograr esta aceleración, el tamiz de campos numéricos tiene que realizar cálculos y factorizaciones en campos numéricos . Esto da como resultado muchos aspectos bastante complicados del algoritmo, en comparación con el tamiz racional más simple.

El tamaño de la entrada al algoritmo es $log 2 n$ o el número de bits en la representación binaria de $n$ . Cualquier elemento del orden $n c$ para una constante $c$ es exponencial en $log n$ . El tiempo de ejecución del tamiz del campo numérico es superpolinomial pero subexponencial en el tamaño de la entrada.

Campos numéricos

Supongamos que $f$ es un polinomio $de k$ grados sobre (los números racionales) y $r$ es una raíz compleja de $f$ . Entonces, $f$ $($ $r$ $) = 0$ , que se puede reordenar para expresar $r$ $k$ como una combinación lineal de potencias de $r$ menor que $k$ . Esta ecuación se puede utilizar para reducir cualquier potencia de $r$ con exponente $e$ $\geq$ $k$ . Por ejemplo, si $f$ $($ $x$ $) =$ $x$ $2$ $+ 1$ y $r$ es la unidad imaginaria $i$ , entonces $i$ $2$ $+ 1 = 0$ , o $i$ $2$ $= -1$ . Esto nos permite definir el producto complejo: ${\textstyle \mathbb {Q} }$

{\begin{alineado}(a+bi)(c+di)&=ac+(ad+bc)i+(bd)i^{2}\\[4pt]&=(ac-bd)+( anuncio+bc)i.\end{aligned}}

En general, esto lleva directamente al campo de números algebraicos , que puede definirse como el conjunto de números complejos dado por: ${\textstyle \mathbb {Q} [r]}$

a_{k-1}r^{k-1}+\cdots +a_{1}r^{1}+a_{0}r^{0},{\text{ donde }}a_{0 },\ldots ,a_{k-1}\in \mathbb {Q}.

El producto de dos de estos valores se puede calcular tomando el producto como polinomios y luego reduciendo cualquier potencia de $r$ con exponente $e$ $\geq$ $k$ como se describió anteriormente, obteniendo un valor en la misma forma. Para garantizar que este campo sea realmente $k$ -dimensional y no colapse en un campo aún más pequeño, es suficiente que $f$ sea un polinomio irreducible sobre los racionales. De manera similar, se puede definir el anillo de números enteros como el subconjunto del cual son raíces de polinomios mónicos con coeficientes enteros. En algunos casos, este anillo de números enteros es equivalente al anillo . Sin embargo, hay muchas excepciones, como cuando d $es$ congruente con 1 módulo 4. ^[2] ${\textstyle \mathbb {O} _ {\mathbb {Q} [r]}}$ ${\textstyle \mathbb {Q} [r]}$ ${\textstyle \mathbb {Z} [r]}$ ${\textstyle \mathbb {Q} [{\sqrt {r}}\,]}$

Método

Se eligen dos polinomios f ( x ) y g ( x ) de pequeños grados d y e , que tienen coeficientes enteros, que son irreducibles sobre los racionales , y que, al interpretarse mod n , tienen una raíz entera común m . Se desconoce una estrategia óptima para elegir estos polinomios; Un método simple es elegir un grado d para un polinomio, considerar la expansión de n en base m (permitiendo dígitos entre − m y m ) para un número de m diferentes de orden n ^{1/ d} , y elegir f ( x ) como el polinomio con los coeficientes más pequeños y g ( x ) como x − m .

Considere los anillos de campo numérico 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 números enteros, también lo será b ^d · f ( a / b ), al que llamamos r . De manera similar, s = b ^e · g ( a / b ) es un número entero. El objetivo es encontrar valores enteros de a y b que simultáneamente hagan que r y s sean suaves en relación con la base de números primos elegida. Si a y b son pequeños, entonces r y s también serán pequeños, aproximadamente del tamaño de m , y tenemos más posibilidades de que sean suaves al mismo tiempo. El enfoque actual más conocido para esta búsqueda es el tamizado en red ; Para obtener rendimientos aceptables, es necesario utilizar una base de factores grande.

Teniendo suficientes pares de este tipo, utilizando la eliminación gaussiana , se puede obtener que los productos de ciertos r y de los s correspondientes sean cuadrados al mismo tiempo. Se necesita una condición ligeramente más estricta: que sean normas de cuadrados en nuestros campos numéricos, pero esa condición también se puede lograr mediante este método. Cada r es una norma de a − r ₁b y, por 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 de f y g mod n , existen homomorfismos de los anillos Z [ r ₁ ] y Z [ r ₂ ] al anillo Z / n Z (los enteros módulo n ), que asignan r ₁ y r ₂ a m , y estos homomorfismos asignarán cada "raíz cuadrada" (normalmente no representada como un número racional) a su representante entero. Ahora el producto de los factores a − mb mod n se puede obtener como un cuadrado de dos maneras: una para cada homomorfismo. Por lo tanto, se pueden encontrar dos números x e y , con x ² − y ² divisible por n y nuevamente con una probabilidad de al menos la mitad obtenemos un factor de n al encontrar el máximo común divisor de n y x − y .

Mejorando la elección del polinomio

La elección del polinomio puede afectar drásticamente el tiempo necesario para completar el resto del algoritmo. El método de elección de polinomios basado en la expansión de $n$ en base $m$ que se muestra arriba es subóptimo en muchas situaciones prácticas, lo que lleva al desarrollo de mejores métodos.

Murphy y Brent sugirieron uno de esos métodos; ^[3] introducen una puntuación de dos partes para los polinomios, basada en la presencia de raíces de módulo primos pequeños y en el valor medio que el polinomio toma en el área de tamizado.

Los mejores resultados reportados ^[4] se lograron mediante el método de Thorsten Kleinjung, ^[5] que permite $g (x) = ax + b$ , y busca sobre $un$ compuesto de pequeños factores primos congruentes con 1 módulo 2 $d$ y sobre los coeficientes principales de $f$ que son divisibles por 60.

Implementaciones

Algunas implementaciones se centran en una determinada clase de números más pequeña. Éstas se conocen como técnicas de tamizado de campo numérico especial , como las utilizadas en el proyecto Cunningham . Un proyecto llamado NFSNET se ejecutó desde 2002 ^[6] hasta al menos 2007. Utilizaba computación distribuida voluntaria en Internet . ^[7]Paul Leyland del Reino Unido y Richard Wackerbarth de Texas estuvieron involucrados. ^[8]

Hasta 2007, la implementación estándar era un conjunto de software desarrollado y distribuido por CWI en los Países Bajos, que sólo estaba disponible bajo una licencia relativamente restrictiva. ^{[ cita necesaria ]} En 2007, Jason Papadopoulos desarrolló una implementación más rápida del procesamiento final como parte de msieve, que es de dominio público. Ambas implementaciones presentan la capacidad de distribuirse entre varios nodos en un clúster con una interconexión suficientemente rápida.

La selección polinomial normalmente se realiza mediante software GPL escrito por Kleinjung, o mediante msieve, y el tamizado reticular mediante software GPL escrito por Franke y Kleinjung; estos se distribuyen en GGNFS.

NFS@Inicio
GGNFS
factor por gnfs
CADO-NFS
msieve (que contiene código de procesamiento final, una selección de polinomios optimizada para números más pequeños y una implementación del tamiz de líneas)
kmGNFS

Ver también

Tamiz de campo de números especiales

Notas

^ Pomerance, Carl (diciembre de 1996). "Una historia de dos tamices" (PDF) . Avisos de la AMS . vol. 43, núm. 12. págs. 1473-1485.
^ Ribenboim, Paulo (1972). Números algebraicos . Wiley-Interscience. ISBN 978-0-471-71804-8.
^ Murphy, B.; Brent, RP (1998), "Sobre polinomios cuadráticos para el tamiz de campo numérico", Australian Computer Science Communications , 20 : 199–213
^ Franke, Jens (2006), Sobre RSA 200 y proyectos más grandes (PDF)
^ Kleinjung, Thorsten (octubre de 2006). "Sobre la selección de polinomios para el tamiz de campos numéricos generales" (PDF) . Matemáticas de la Computación . 75 (256): 2037-2047. Código Bib : 2006MaCom..75.2037K. doi : 10.1090/S0025-5718-06-01870-9 . Consultado el 13 de diciembre de 2007 .
^ Paul Leyland (12 de diciembre de 2003). "NFSNET: el primer año". Presentación en Taller EIDMA-CWI sobre Factorización de Números Grandes . Consultado el 9 de agosto de 2011 .
^ "Bienvenido a NFSNET". 23 de abril de 2007. Archivado desde el original el 22 de octubre de 2007 . Consultado el 9 de agosto de 2011 .
^ "Acerca de NFSNET". Archivado desde el original el 9 de mayo de 2008 . Consultado el 9 de agosto de 2011 .

Referencias

Arjen K. Lenstra y HW Lenstra, Jr. (eds.). "El desarrollo del tamiz de campo numérico". Apuntes de clases de matemáticas. (1993) 1554. Springer-Verlag.
Richard Crandall y Carl Pomerance . Números primos: una perspectiva computacional (2001). 2ª edición, Springer. ISBN 0-387-25282-7 . Sección 6.2: Criba de campos numéricos, págs. 278–301.

Matthew E. Briggs: Introducción al tamiz de campo numérico general, 1998