Tamiz de campo de números especiales

En teoría de números , una rama de las matemáticas , el tamiz de campo numérico especial (SNFS) es un algoritmo de factorización de enteros de propósito especial . De allí se derivó el tamiz de campo numérico general (GNFS).

El tamiz de campo numérico especial es eficaz para números enteros de la forma r ^e ± s , donde r y s son pequeños (por ejemplo, los números de Mersenne ).

Heurísticamente , su complejidad para factorizar un número entero es de la forma: ^[1] ${\displaystyle n}$

${\displaystyle \exp \left(\left(1+o(1)\right)\left({\tfrac {32}{9}}\log n\right)^{1/3}\left(\log \log n\right)^{2/3}\right)=L_{n}\left[1/3,(32/9)^{1/3}\right]}$

en notaciones O y L.

El SNFS ha sido utilizado ampliamente por NFSNet (un esfuerzo informático distribuido voluntario ), NFS@Home y otros para factorizar números del proyecto Cunningham ; Desde hace algún tiempo, los registros para la factorización de números enteros son números factorizados por SNFS.

Descripción general del método

El SNFS se basa en una idea similar al tamiz racional, mucho más simple ; en particular, a los lectores les puede resultar útil leer primero sobre el tamiz racional , antes de abordar el SNFS.

El SNFS funciona de la siguiente manera. Sea n el número entero que queremos factorizar. Al igual que en el tamiz racional , el SNFS se puede dividir en dos pasos:

• Primero, encuentre una gran cantidad de relaciones multiplicativas entre una base factorial de elementos de Z / n Z , de modo que la cantidad de relaciones multiplicativas sea mayor que la cantidad de elementos en la base factorial.
• En segundo lugar, multiplique subconjuntos de estas relaciones de tal manera que todos los exponentes sean pares, lo que dará como resultado congruencias de la forma a ² ≡ b ² ( mod n ). Estos, a su vez, conducen inmediatamente a factorizaciones de n : n = mcd ( a + b , n ) × mcd( a - b , n ). Si se hace correctamente, es casi seguro que al menos una de esas factorizaciones no será trivial.

El segundo paso es idéntico al caso del tamiz racional y es un problema sencillo de álgebra lineal . Sin embargo, el primer paso se realiza de una manera diferente y más eficiente que el tamiz racional, utilizando campos numéricos .

Detalles del método

Sea n el número entero que queremos factorizar. Elegimos un polinomio irreducible f con coeficientes enteros y un número entero m tal que f ( m )≡0 ( mod n ) (explicaremos cómo se eligen en la siguiente sección). Sea α una raíz de f ; entonces podemos formar el anillo Z [α]. Hay un homomorfismo de anillo único φ de Z [ α ] a Z /n Z que asigna α a m . Por simplicidad, asumiremos que Z [ α ] es un dominio de factorización único ; el algoritmo se puede modificar para que funcione cuando no lo es, pero existen algunas complicaciones adicionales.

A continuación, configuramos dos bases de factores paralelas , una en Z [ α ] y otra en Z . El de Z [ α ] consta de todos los ideales primos de Z [ α ] cuya norma está acotada por un valor elegido . La base factorial en Z , como en el caso del tamiz racional, consta de todos los números primos hasta algún otro límite. ${\displaystyle N_{\max }}$

Luego buscamos pares de números enteros relativamente primos ( a , b ) tales que:

• a + bm es suave con respecto a la base factorial en Z (es decir, es un producto de elementos en la base factorial).
• a + bα es suave con respecto a la base del factor en Z [ α ]; Dada cómo elegimos la base del factor, esto equivale a que la norma de que a + bα sea divisible sólo por números primos menores que . ${\displaystyle N_{\max }}$

Estos pares se encuentran mediante un proceso de tamizado, análogo al Tamiz de Eratóstenes ; esto motiva el nombre "Number Field Sieve".

Para cada uno de estos pares, podemos aplicar el homomorfismo de anillo φ a la factorización de a + bα , y podemos aplicar el homomorfismo de anillo canónico de Z a Z /n Z a la factorización de a + bm . Igualarlos da una relación multiplicativa entre elementos de una base de factores más grande en Z /n Z , y si encontramos suficientes pares podemos proceder a combinar las relaciones y el factor n , como se describió anteriormente.

Elección de parámetros

No todos los números son una elección apropiada para el SNFS: es necesario conocer de antemano un polinomio f de grado apropiado (se conjetura que el grado óptimo es , que es 4, 5 o 6 para los tamaños de N actualmente factibles de factorizar) con coeficientes pequeños, y un valor x tal que donde N es el número a factorizar. Hay una condición adicional: x debe cumplirse para a y b no mayores que . ${\displaystyle \left(3{\frac {\log N}{\log \log N}}\right)^{\frac {1}{3}}}$ ${\displaystyle f(x)\equiv 0{\pmod {N}}}$ ${\displaystyle ax+b\equiv 0{\pmod {N}}}$ ${\displaystyle N^{1/d}}$

Un conjunto de números para los cuales existen tales polinomios son los números de las tablas de Cunningham ; por ejemplo, cuando NFSNET factorizó , usaron el polinomio con , since y . ${\displaystyle a^{b}\pm 1}$ ${\displaystyle 3^{479}+1}$ ${\displaystyle x^{6}+3}$ ${\displaystyle x=3^{80}}$ ${\displaystyle (3^{80})^{6}+3=3^{480}+3}$ ${\displaystyle 3^{480}+3\equiv 0{\pmod {3^{479}+1}}}$

Los números definidos por recurrencias lineales, como los números de Fibonacci y Lucas , también tienen polinomios SNFS, pero son un poco más difíciles de construir. Por ejemplo, tiene polinomio y el valor de x satisface . ^[2] ${\displaystyle F_{709}}$ ${\displaystyle n^{5}+10n^{3}+10n^{2}+10n+3}$ ${\displaystyle F_{142}x-F_{141}=0}$

Si ya se conocen algunos factores de un gran número compatibles con SNFS, entonces se podría hacer el módulo de cálculo de SNFS para la parte restante; para el ejemplo de NFSNET anterior, multiplicado por un número compuesto de 197 dígitos (los factores pequeños fueron encontrados por ECM ), y el SNFS se realizó en módulo del número de 197 dígitos. El número de relaciones requeridas por SNFS todavía depende del tamaño del número grande, pero los cálculos individuales son más rápidos módulo cuanto menor es el número. ${\displaystyle 3^{479}+1=(2^{2}\times 158071\times 7167757\times 7759574882776161031)}$

Limitaciones del algoritmo

Este algoritmo, como se mencionó anteriormente, es muy eficiente para números de la forma r ^e ± s , para r y s relativamente pequeños. También es eficaz para cualquier número entero que pueda representarse como un polinomio con coeficientes pequeños. Esto incluye números enteros de la forma más general are ± bs ^f , y también muchos números enteros cuya representación binaria tiene un peso Hamming bajo ^. La razón de esto es la siguiente: El tamiz de campo numérico realiza el tamizado en dos campos diferentes. El primer campo suele ser el de los racionales. El segundo es un campo de grado superior. La eficiencia del algoritmo depende en gran medida de las normas de ciertos elementos en estos campos. Cuando un número entero se puede representar como un polinomio con coeficientes pequeños, las normas que surgen son mucho más pequeñas que las que surgen cuando un número entero se representa mediante un polinomio general. La razón es que un polinomio general tendrá coeficientes mucho mayores y las normas serán correspondientemente mayores. El algoritmo intenta factorizar estas normas sobre un conjunto fijo de números primos. Cuando las normas son más pequeñas, es más probable que estos números se factoricen.

Ver también

• Tamiz de campo de números generales

Referencias

1. Pomerance, Carl (diciembre de 1996), "A Tale of Two Sieves" (PDF) , Avisos de la AMS , vol. 43, núm. 12, págs. 1473-1485
2. Franke, Jens. "Notas de instalación de ggnfs-lasieve4". Instituto de Tecnología de Massachusetts del MIT .

Otras lecturas

• Byrnes, Steven (18 de mayo de 2005), "The Number Field Sieve" (PDF) , Matemáticas 129
• Lenstra, Alaska ; Lenstra, HW Jr .; Manasse, MS y Pollard, JM (1993), "La factorización del noveno número de Fermat", Matemáticas de la Computación , 61 (203): 319–349, Bibcode :1993MaCom..61..319L, doi : 10.1090/S0025- 5718-1993-1182953-4 , hdl : 1887/2150
• Lenstra, Alaska; Lenstra, HW, Jr., eds. (1993), El desarrollo del tamiz de campo numérico , Lecture Notes in Mathematics, vol. 1554, Nueva York: Springer-Verlag, ISBN 978-3-540-57013-4{{citation}}: Mantenimiento CS1: varios nombres: lista de editores ( enlace )
• Silverman, Robert D. (2007), "Parametrización óptima de SNFS", Journal of Mathematical Cryptology , 1 (2): 105–124, CiteSeerX  10.1.1.12.2975 , doi :10.1515/JMC.2007.007, S2CID  16236028