Tamiz de campo numérico general

En teoría de números , la criba 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 de la criba de cuerpos de números especiales : mientras que esta última solo puede factorizar números de una cierta forma especial, la criba de cuerpos de números generales puede factorizar cualquier número excepto las potencias primas (que son triviales de factorizar tomando raíces).

El principio de la criba de cuerpos numéricos (tanto especial como general) puede entenderse como una mejora de la criba racional más simple o criba cuadrática . Cuando se utilizan tales algoritmos para factorizar un número grande $n$ , es necesario buscar números lisos (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). La criba de cuerpos numéricos general, por otro lado, logra buscar números lisos 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 lisos que los números inspeccionados en algoritmos anteriores. Esta es la clave de la eficiencia de la criba de cuerpos numéricos. Para lograr esta aceleración, la criba de cuerpos numéricos tiene que realizar cálculos y factorizaciones en cuerpos numéricos . Esto da como resultado muchos aspectos bastante complicados del algoritmo, en comparación con la criba racional más simple.

El tamaño de la entrada del 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 de la criba 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 grado $k$ sobre (los números racionales), y $r$ es una raíz compleja de $f$ . Entonces, $f$ $($ $r$ $) = 0$ , que puede reorganizarse para expresar $r$ $k$ como una combinación lineal de potencias de $r$ menores que $k$ . Esta ecuación puede usarse 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{aligned}(a+bi)(c+di)&=ac+(ad+bc)i+(bd)i^{2}\\[4pt]&=(ac-bd)+(ad+bc)i.\end{aligned}}

En general, esto conduce directamente al cuerpo numérico algebraico , 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 valores cualesquiera de estos puede calcularse 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 asegurar que este campo es realmente $k$ -dimensional y no colapsa a un campo aún más pequeño, es suficiente que $f$ sea un polinomio irreducible sobre los racionales. De manera similar, uno puede definir el anillo de números enteros como el subconjunto de los cuales 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. ^[2] ${\textstyle \mathbb {O} _ {\mathbb {Q} [r]}}$ ${\textstyle \mathbb {Q} [r]}$ ${\textstyle \mathbb {Z} [r]}$

Método

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 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 .

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 . Puesto que f es de grado d con coeficientes enteros, si a y b son enteros, entonces también lo será b ^d · f ( a / b ), al 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 en relación con la base elegida de primos. 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 una mejor posibilidad de que sean suaves al mismo tiempo. El enfoque actual más conocido para esta búsqueda es el tamizado reticular ; para obtener rendimientos aceptables, es necesario utilizar una base de factores grande.

Teniendo suficientes pares de este tipo, usando la eliminación gaussiana , se pueden obtener productos de ciertos r y de los s correspondientes para que sean cuadrados al mismo tiempo. Se necesita una condición ligeramente más fuerte: que sean normas de cuadrados en nuestros cuerpos numéricos, pero esa 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 un 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. Debe notarse que el uso de la eliminación gaussiana no da 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 .

Como m es una raíz tanto de f como de g mod n , hay homomorfismos desde los anillos Z [ r ₁ ] y Z [ r ₂ ] hasta el 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 bien, el producto de los factores a − mb mod n se puede obtener como un cuadrado de dos formas: una para cada homomorfismo. Así, se pueden encontrar dos números x e y , con x ² − y ² divisible por n y, de nuevo, con probabilidad de al menos la mitad, obtenemos un factor de n hallando el máximo común divisor de n y x − y .

Mejorando la elección de polinomios

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 no es óptimo en muchas situaciones prácticas, lo que lleva al desarrollo de mejores métodos.

Murphy y Brent sugirieron un método de este tipo; ^[3] introducen una puntuación de dos partes para polinomios, basada en la presencia de raíces módulo primos pequeños y en el valor promedio que el polinomio toma sobre 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 $a$ compuesto de pequeños factores primos congruentes con 1 módulo 2 $d$ y sobre coeficientes principales de $f$ que son divisibles por 60.

Implementaciones

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

Hasta 2007, la implementación estándar era un paquete de software desarrollado y distribuido por CWI en los Países Bajos, que estaba disponible solo bajo una licencia relativamente restrictiva. ^{[ cita requerida ]} 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 cuentan con la capacidad de distribuirse entre varios nodos en un clúster con una interconexión suficientemente rápida.

La selección de polinomios normalmente se realiza mediante software GPL escrito por Kleinjung, o por msieve, y el cribado de red mediante software GPL escrito por Franke y Kleinjung; estos se distribuyen en GGNFS.

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

Véase también

Tamiz de campo de número especial

Notas

^ Pomerance, Carl (diciembre de 1996). "A Tale of Two Sieves" (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 la criba del cuerpo 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 la criba de cuerpos numéricos generales" (PDF) . Matemáticas de la computación . 75 (256): 2037–2047. Bibcode :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 el 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 de la criba del campo numérico". Apuntes de clase en 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: Tamiz de cuerpos numéricos, págs. 278–301.

Matthew E. Briggs: Introducción a la criba de campo numérico general, 1998