En teoría de números , el tamiz 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) tiene la forma
(en notación L ), donde ln es el logaritmo natural . [1] Es una generalización del tamiz de campo numérico especial : mientras que este último solo puede factorizar números de una determinada forma especial, el tamiz de campo numérico general puede factorizar cualquier número aparte de las potencias primas (que son triviales de factorizar tomando raíces) .
El principio del tamiz de campo numérico (tanto especial como general) puede entenderse como una mejora del tamiz racional más simple o tamiz cuadrático . Cuando se utilizan estos algoritmos para factorizar un gran número n , es necesario buscar números suaves (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). El tamiz de campo numérico general, por otro lado, logra buscar números suaves que son subexponenciales en el tamaño de n. Dado que estos números son más pequeños, es más probable que sean uniformes que los números inspeccionados en algoritmos anteriores. Esta es la clave de la eficiencia del tamiz de campo numérico. Para lograr esta aceleración, el tamiz de campo numérico debe realizar cálculos y factorizaciones en campos numéricos . Esto da como resultado muchos aspectos bastante complicados del algoritmo, en comparación con el tamiz racional más simple.
El tamaño de la entrada al 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 del tamiz de campo numérico es superpolinomial pero subexponencial en el tamaño de la entrada.
Suponga que f es un polinomio de k grados sobre Q (los números racionales), y r es una raíz compleja de f . Entonces, f ( r ) = 0 , que se puede reorganizar para expresar r k como una combinación lineal de potencias de r menor que k . Esta ecuación se puede utilizar para reducir cualquier potencia de r con exponente e ≥ 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:
En general, esto conduce directamente al campo numérico algebraico Q [ r ] , que se puede definir como el conjunto de números complejos dado por: