Método de tamiz de campo numérico especial

El método de criba de campo numérico especial ( en inglés special number field sieve , SNFS) es un método para factorizar enteros de un tipo especial. De él se derivó el método general de tamiz de campos numéricos , que es el algoritmo de factorización más eficiente para números enteros grandes . El método es eficaz para números enteros de la forma r e ± s , donde r N s Z, r y s son pequeños (por ejemplo , números de Mersenne ). $n>10^{{110}}$ $\en$ $\en$

La estimación heurística de la complejidad de factorización del número n se expresa mediante la fórmula [1] :

e^{\left(1+o(1)\right)\left({\frac {32}{9}}\log n\right)^{\frac {1}{3}}\left (\log \log n\right)^{\frac {2}{3}}}=L_{n}\left[1/3,(32/9)^{1/3}\right]

Utilizando SNFS, se factorizó el número de Fermat que contiene 155 dígitos decimales [2] . $F_{9}=2^{512}+1$

Orígenes

La idea básica del método fue propuesta por primera vez John Pollard su artículo [3] que envió a sus colegas en 1988. En él, ilustraba su método sobre el séptimo número de Fermat . La idea era realizar el tamizado no en un anillo de números enteros, como en el método del tamiz cuadrático , sino en un campo numérico algebraico. En 1990, el noveno número de Fermat se descompuso utilizando este método . Inicialmente, el método era aplicable solo para números de una forma especial 2 n ± c , por lo que se denominó "método de tamiz de campo de número especial". El método se modificó más tarde para números arbitrarios y se denominó método de tamiz numérico general . ${\ estilo de visualización 2^{128}+1}$ $F_{9}=2^{512}+1$

Descripción general del método

SNFS se basa en el método de tamiz racional más simple . Se anima al lector a familiarizarse con este método antes de aprender acerca de SNFS.

SNFS funciona así. Sea n el número a factorizar. Similar al método de tamiz racional, el algoritmo SNFS se puede dividir en dos pasos:

Hallar el número de razones multiplicativas de la base factorial Z / n Z mayor que el número de elementos de la base factorial.
Multiplicando las razones entre sí de manera que los grados de los productos resultantes sean iguales, es decir, obteniendo razones de la forma a 2 ≡ b 2 ( mod n ). Esto a su vez conduce a una factorización de n : n = mcd ( a + b , n ) × mcd( a - b , n ). Si la descomposición obtenida es trivial (es decir, n = n × 1), se deben buscar otros productos de relaciones que satisfagan esta condición.

El segundo paso es idéntico al paso del método del tamiz racional y es un problema de álgebra lineal . A diferencia del primer paso, que en este método es más eficiente.

Detalles del método

Sea n un número factorizable. Tome un polinomio irreducible f y un entero m tal que f ( m ) ≡ 0 ( mod n ) (los principios para elegirlos se explicarán en la siguiente sección). Sea α la raíz de f ; entonces hay un anillo Z [α]. Entonces hay un único anillo de homomorfismo φ entre Z [ α ] y Z /n Z que asigna α a m . Por simplicidad, asumimos que Z [ α ] es un anillo factorial ; el método puede modificarse para el caso en que no se cumpla esta condición, lo que dará lugar a cálculos adicionales.

Luego creamos dos bases factoriales , una para Z [ α ] y otra para Z. La base factorial Z [ α ] contiene todos los números primos Z [ α ] cuyo tamaño está limitado por . La base factorial Z , como en el método de tamiz racional, consta de números primos hasta algún número límite. ${\ Displaystyle N_ {\ max}}$

Luego buscamos números coprimos ( a , b ) tales que:

a + bm es suave con respecto a los elementos de la base factorial de Z (es decir, todos sus divisores primos están contenidos en la base factorial).
a + bα es suave con respecto a los elementos de la base factorial Z [ α ]; por la forma en que elegimos los elementos de la base factorial, esta condición es equivalente al hecho de que a + bα es divisible solo por números primos menores que . ${\ Displaystyle N_ {\ max}}$

Estos pares de números se encuentran por un método de tamizado similar al tamiz de Eratóstenes ; esto explica el nombre del método de tamiz de campo numérico.

Para cada par de números ( a , b ) podemos aplicar el anillo de homomorfismo φ para factorizar a + bα y el anillo de homomorfismo canónico de Z a Z /n Z para factorizar a + bm . Igualándolos, obtenemos relaciones multiplicativas para los elementos de la base factorial Z /n Z . Habiendo encontrado un número suficiente de tales proporciones, las multiplicamos entre sí como se describe anteriormente.

Elección de opciones

No todos los números son adecuados para la factorización por el método SNFS: es necesario encontrar de antemano un polinomio f de un grado adecuado (se supone que el grado óptimo es ; para números factorizables en el momento dado, N es 4,5 o 6) con coeficientes pequeños yx tal que , donde N es el número para la factorización . También x debe ser tal que se cumpla para a y b no grandes . $\left(3{\frac {\log N}{\log \log N}}\right)^{1/3}$ $f(x)\equiv 0{\pmod {N))$ $ax+b\equiv 0{\pmod {N))$ ${\ Displaystyle N^{1/d))$

Uno de los tipos de números para los que existen tales polinomios son los números de la forma ; por ejemplo, cuando NFSNET descompuso el número 3^479+1, usaron el polinomio x^6+3 para x=3^80, porque (3^80)^6+3 = 3^480+3 y . $a^{b}\pm 1$ $3^{480}+3\equiv 0{\pmod {3^{479}+1))$

Los números definidos por relaciones de recurrencia lineal, como los números de Fibonacci y los números de Lucas , también tienen polinomios SNFS, pero son un poco más difíciles de obtener. Por ejemplo, tiene un polinomio y un valor de x que satisface . [cuatro] ${\ Displaystyle F_ {709}}$ ${\ estilo de visualización n^{5}+10n^{3}+10n^{2}+10n+3}$ $F_{142}x-F_{141}=0$

Si conoce algunos divisores de un número SNFS grande, puede hacer cálculos SNFS para el resto; para el ejemplo anterior de NFSNET, 3^479+1 = (4 158071 7167757 7759574882776161031) multiplicado por un número compuesto de 197 dígitos (los pequeños divisores se eliminaron mediante el método ECM ), y se aplicó SNFS para un número de 197 dígitos. El número de operaciones para NFS depende del tamaño del número original, pero algunos cálculos son más rápidos que un número más pequeño.

Restricciones

Este método, como se señaló anteriormente, es muy eficiente para números de la forma r e ± s , donde r y s son relativamente pequeños. También es efectivo para números que se pueden representar como un polinomio con coeficientes pequeños. El hecho es que el método especial de tamiz de campos numéricos tamiza dos campos numéricos. La efectividad del método depende en gran medida del tamaño de ciertos elementos en estos campos. Si un número se puede representar como un polinomio con coeficientes pequeños, los números que se calculan son mucho más pequeños que los números con los que uno tiene que lidiar si dicho polinomio no existe.

Véase también

Método de tamiz de campo numérico general

Notas

↑ Pomerance, Carl (diciembre de 1996), A Tale of Two Sieves , Notices of the AMS Vol . 43 (12): 1473–1485 , < http://www.ams.org/notices/199612/pomerance.pdf > Archivado copia fechada el 11 de noviembre de 2020 en Wayback Machine
↑ Vasilenko, O. N. (2003), Algoritmos criptográficos de teoría numérica , p. 93-107 , < http://www.ict.edu.ru/ft/002416/book.pdf > Archivado el 27 de enero de 2007 en Wayback Machine .
↑ Pollard, JM (1988), Factorización con números cúbicos
↑ Franke, Jens Notas de instalación para ggnfs-lasieve4 . Instituto Tecnológico de Massachusetts del MIT . Consultado el 4 de diciembre de 2011. Archivado desde el original el 5 de septiembre de 2012. (indefinido)

Literatura

Ishmukhametov, Sh.T. (2011), Métodos de factorización para números naturales , p. 145-175 , < http://window.edu.ru/window_catalog/files/r73980/Monograph_ishm.pdf > (enlace no disponible)
Byrnes, Steven (18 de mayo de 2005), The Number Field Sieve , Math 129 , < http://modular.fas.harvard.edu/129-05/final_papers/Steve_Byrnes.pdf > . Consultado el 4 de diciembre de 2011. Archivado el 20 de septiembre de 2006 en Wayback Machine .
Lenstra, A.K .; Lenstra, HW, Jr. ; Manasse, MS y Pollard, JM (1993), La factorización del noveno número de Fermat , Matemáticas de computación Vol. 61 (203): 319–349, doi : 10.1090/S0025-5718-1993-1182953-4 , < http: //www.std.org/~msm/common/f9paper.ps > Archivado el 4 de febrero de 2012 en Wayback Machine .
Lenstra, AK y Lenstra, HW, Jr., eds. (1993), The Development of the Number Field Sieve , vol. 1554, Lecture Notes in Mathematics, Nueva York: Springer-Verlag, ISBN 3540570136
Silverman, Robert D. (2007), Parametrización óptima de SNFS, J. Criptología matemática (de Gruyter) . — Vol. 1: 105–124

Enlaces

NFS@Inicio