En teoría de números , una rama de las matemáticas , la criba de cuerpos numéricos especiales (SNFS, por sus siglas en inglés) es un algoritmo de factorización de números enteros de propósito especial . La criba de cuerpos numéricos generales (GNFS, por sus siglas en inglés) se derivó de ella.
La criba de campos numéricos especiales es eficiente para números enteros de la forma r e ± s , donde r y s son pequeños (por ejemplo, números de Mersenne ).
Heurísticamente , su complejidad para factorizar un entero es de la forma: [1]
en notaciones O y L.
El SNFS ha sido ampliamente utilizado por NFSNet (un esfuerzo voluntario de computación distribuida ), 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.
El SNFS se basa en una idea similar a la del tamiz racional mucho más simple ; en particular, los lectores pueden encontrar útil leer sobre el tamiz racional primero, antes de abordar el SNFS.
El SNFS funciona de la siguiente manera. Sea n el entero que queremos factorizar. Al igual que en la criba racional , el SNFS se puede dividir en dos pasos:
El segundo paso es idéntico al caso de la criba racional y es un problema de álgebra lineal sencillo . Sin embargo, el primer paso se realiza de una manera diferente y más eficiente que la criba racional, utilizando cuerpos numéricos .
Sea n el 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 asigna α a m . Para simplificar, supondremos que Z [ α ] es un dominio de factorización único ; el algoritmo se puede modificar para que funcione cuando no lo es, pero entonces hay algunas complicaciones adicionales.
A continuación, establecemos dos bases factoriales paralelas , una en Z [ α ] y otra en Z . La de Z [ α ] consta de todos los ideales primos en Z [ α ] cuya norma está limitada por un valor elegido . La base factorial en Z , como en el caso de la criba racional, consta de todos los números enteros primos hasta algún otro límite.
Luego buscamos pares de números enteros relativamente primos ( a , b ) tales que:
Estos pares se encuentran a través de un proceso de tamizado, análogo al Tamiz de Eratóstenes ; esto motiva el nombre de "Tamiz de Campo de Números".
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 . Al igualarlos obtenemos una relación multiplicativa entre elementos de una base factorial mayor en Z /n Z , y si encontramos suficientes pares podemos proceder a combinar las relaciones y factorizar n , como se describió anteriormente.
No todos los números son una opción apropiada para la SNFS: es necesario conocer de antemano un polinomio f de grado apropiado (se supone que el grado óptimo es , que es 4, 5 o 6 para los tamaños de N que actualmente son 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 satisfacer para a y b no mayores que .
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ó , utilizaron el polinomio con , ya que , y .
Los números definidos por recurrencias lineales, como los números de Fibonacci y Lucas , también tienen polinomios SNFS, pero estos son un poco más difíciles de construir. Por ejemplo, tiene polinomio , y el valor de x satisface . [2]
Si ya se conocen algunos factores de un número grande compatible con SNFS, entonces se podría hacer el cálculo SNFS módulo la parte restante; para el ejemplo NFSNET anterior, multiplicado por un número compuesto de 197 dígitos (los factores pequeños se encontraron mediante ECM ), y el SNFS se realizó módulo el 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 el número más pequeño.
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 eficiente para cualquier 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 bajo peso de Hamming. La razón de esto es la siguiente: el tamiz de campos numéricos 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 entero puede representarse como un polinomio con coeficientes pequeños, las normas que surgen son mucho más pequeñas que las que surgen cuando un 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 tengan en cuenta.
![{\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f20005fbc2e025704962638fd9a5283137c3159)
