En la 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 . El tamiz de campo numérico general (GNFS) se derivó de él.
El tamiz especial campo de número es eficiente para los enteros de la forma r e ± s , donde r y s son pequeñas (por ejemplo números de Mersenne ).
Heurísticamente , su complejidad para factorizar un enterotiene la forma: [1]
en O y L-notaciones .
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 ; Durante algún tiempo, los registros de factorización de enteros han sido números factorizados por SNFS.
Resumen del método
El SNFS se basa en una idea similar al tamiz racional mucho más simple ; en particular, los lectores pueden encontrar ú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 un gran número de relaciones multiplicativas entre una base de factores de elementos de Z / n Z , de modo que el número de relaciones multiplicativas sea mayor que el número de elementos en la base de factores.
- En segundo lugar, multiplique subconjuntos de estas relaciones de tal manera que todos los exponentes sean pares, lo que resultará en congruencias de la forma a 2 ≡ b 2 ( mod n ). Estos, a su vez, conducen inmediatamente a factorizaciones de n : n = mcd ( a + b , n ) × mcd ( a - b , n ). Si se hace bien, 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 sencillo problema de álgebra lineal . El primer paso, sin embargo, 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 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 mapea α a m . Para simplificar, asumiremos que Z [ α ] es un dominio de factorización único ; el algoritmo se puede modificar para que funcione cuando no lo es, pero luego hay algunas complicaciones adicionales.
A continuación, se estableció dos paralelas bases de factores , uno en Z [ α ] y uno en Z . El de Z [ α ] consta de todos los ideales primos en Z [ α ] cuya norma está limitada por un valor elegido. La base de factores en Z , como en el caso del tamiz racional, consta de todos los números primos hasta algún otro límite.
Luego buscamos pares de números enteros relativamente primos ( a , b ) tales que:
- a + bm es suave con respecto a la base de factores en Z (es decir, es un producto de elementos en la base de factores).
- a + bα es suave con respecto al factor base en Z [ α ]; dado cómo elegimos la base de factores, esto equivale a que la norma de a + bα sea divisible solo por primos menores que.
Estos pares se encuentran mediante un proceso de tamizado, análogo al Tamiz de Eratóstenes ; esto motiva el nombre "Número de tamiz de campo".
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 . Establecer estos iguales da una relación multiplicativa entre elementos de una base de factores mayor 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 opción adecuada 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 quedonde N es el número a factorizar. Hay una condición adicional: x debe satisfacer para ayb no más grande que .
Un conjunto de números para los que existen tales polinomios son los números de las mesas de Cunningham ; por ejemplo, cuando NFSNET factorizó 3 ^ 479 + 1, usaron el polinomio x ^ 6 + 3 con x = 3 ^ 80, ya que (3 ^ 80) ^ 6 + 3 = 3 ^ 480 + 3, y.
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]
Si ya conoce algunos factores de un número SNFS grande, puede hacer el cálculo de SNFS en el módulo restante; para el ejemplo de NFSNET anterior, 3 ^ 479 + 1 = (4 * 158071 * 7167757 * 7759574882776161031) multiplicado por un número compuesto de 197 dígitos (los factores pequeños fueron eliminados por ECM ), y el SNFS se realizó en módulo el número de 197 dígitos. El número de relaciones requeridas por SNFS aún depende del tamaño del número grande, pero los cálculos individuales son más rápidos módulo el número más pequeño.
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ño. También es eficiente para cualquier número entero que pueda representarse como un polinomio con coeficientes pequeños. Esto incluye enteros de la forma más general ar e ± bs f , y también para muchos 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 está representado por 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
Referencias
- ^ Pomerance, Carl (diciembre de 1996), "Una historia de dos tamices" (PDF) , Avisos de la AMS , 43 (12), págs. 1473-1485
- ^ Franke, Jens. "Notas de instalación para ggnfs-lasieve4" . MIT Instituto de Tecnología de Massachusetts.
Otras lecturas
- Byrnes, Steven (18 de mayo de 2005), "The Number Field Sieve" (PDF) , Matemáticas 129
- Lenstra, AK ; Lenstra, HW, Jr .; Manasse, MS & Pollard, JM (1993), "The Factorization of the Ninth Fermat Number" , Mathematics of Computation , 61 (203): 319–349, Bibcode : 1993MaCom..61..319L , doi : 10.1090 / S0025- 5718-1993-1182953-4
- Lenstra, AK; Lenstra, HW, Jr., eds. (1993), The Development of the Number Field Sieve , Lecture Notes in Mathematics, 1554 , Nueva York: Springer-Verlag, ISBN 978-3-540-57013-4
- 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