En teoría de números, la criba general del cuerpo de números (del inglés general number field sieve (GNFS) es el más eficiente algoritmo clásico conocido para factorizar enteros mayores de 100 dígitos. Heurísticamente, su complejidad para factorizar un entero n (consistente en log2n bits) es de la forma
(en notación L), donde ln es el logaritmo en base e.[1] Es una generalización de la criba especial del cuerpo de números: mientras que el último puede factorizar únicamente números de una cierta forma especial, la criba general del cuerpo de números puede factorizar cualquier número aparte de potencias primas (que es trivial factorizar tomando raíces). Cuando el término en inglés number field sieve (NFS) es usado sin calificación, este se refiere a la criba general del cuerpo de números.
El principio de la criba del cuerpo de números (ambas, especial y general) se puede entender como una mejora de la más simple criba racional o criba cuadrática. Cuando se usan tales algoritmos para factorizar un número grande n, es necesaria la búsqueda de números lisos (i.e. números con factores primos pequeños) de orden n1/2. El tamaño de esos valores es exponencial en el tamaño de n (véase después). La criba general del cuerpo de números, por otra parte, gestiona la búsqueda de números lisos que sean subexponenciales en el tamaño de n. Puesto que esos números son más pequeños, son más propensos a ser lisos que los números evaluados en los algoritmos anteriores. Esta es la clave de la eficiencia de la criba del cuerpo de números. Con el fin de lograr esta aceleración, la criba del cuerpo de números tiene que realizar los cálculos y factorizaciones en cuerpos numéricos. Esto resulta en muchos aspectos lo más complicado del algoritmo, si lo comparamos con la más simple criba racional.
Nótese que log2n es el número de bits en la representación binaria del n, que es el tamaño de la entrada para el algoritmo, así que cualquier elemento de orden nc para una constante c es exponencial en log n. El tiempo de ejecución de la criba del cuerpo de números es super-polinomial pero sub-exponencial en el tamaño de la entrada.
Pomerance, Carl (diciembre de 1996). «A Tale of Two Sieves» (PDF). Notices of the AMS43 (12). pp. 1473-1485.
Arjen K. Lenstra and H. W. Lenstra, Jr. (eds.). "The development of the number field sieve". Lecture Notes in Math. (1993) 1554. Springer-Verlag.
Richard Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective (2001). 2nd edition, Springer. ISBN 0-387-25282-7. Section 6.2: Number field sieve, pp. 278–301.
Datos:Q140770
Agosto 04, 2021
criba, general, cuerpo, números, teoría, números, criba, general, cuerpo, números, inglés, general, number, field, sieve, gnfs, más, eficiente, algoritmo, clásico, conocido, para, factorizar, enteros, mayores, dígitos, heurísticamente, complejidad, para, facto. En teoria de numeros la criba general del cuerpo de numeros del ingles general number field sieve GNFS es el mas eficiente algoritmo clasico conocido para factorizar enteros mayores de 100 digitos Heuristicamente su complejidad para factorizar un entero n consistente en log2 n bits es de la forma exp 64 9 3 o 1 ln n 1 3 ln ln n 2 3 L n 1 3 64 9 3 displaystyle exp left left sqrt 3 frac 64 9 o 1 right ln n frac 1 3 ln ln n frac 2 3 right L n left frac 1 3 sqrt 3 frac 64 9 right en notacion L donde ln es el logaritmo en base e 1 Es una generalizacion de la criba especial del cuerpo de numeros mientras que el ultimo puede factorizar unicamente numeros de una cierta forma especial la criba general del cuerpo de numeros puede factorizar cualquier numero aparte de potencias primas que es trivial factorizar tomando raices Cuando el termino en ingles number field sieve NFS es usado sin calificacion este se refiere a la criba general del cuerpo de numeros El principio de la criba del cuerpo de numeros ambas especial y general se puede entender como una mejora de la mas simple criba racional o criba cuadratica Cuando se usan tales algoritmos para factorizar un numero grande n es necesaria la busqueda de numeros lisos i e numeros con factores primos pequenos de orden n1 2 El tamano de esos valores es exponencial en el tamano de n vease despues La criba general del cuerpo de numeros por otra parte gestiona la busqueda de numeros lisos que sean subexponenciales en el tamano de n Puesto que esos numeros son mas pequenos son mas propensos a ser lisos que los numeros evaluados en los algoritmos anteriores Esta es la clave de la eficiencia de la criba del cuerpo de numeros Con el fin de lograr esta aceleracion la criba del cuerpo de numeros tiene que realizar los calculos y factorizaciones en cuerpos numericos Esto resulta en muchos aspectos lo mas complicado del algoritmo si lo comparamos con la mas simple criba racional Notese que log2 n es el numero de bits en la representacion binaria del n que es el tamano de la entrada para el algoritmo asi que cualquier elemento de orden nc para una constante c es exponencial en log n El tiempo de ejecucion de la criba del cuerpo de numeros es super polinomial pero sub exponencial en el tamano de la entrada Vease tambien EditarCriba especial del cuerpo de numerosReferencias Editar Pomerance Carl diciembre de 1996 A Tale of Two Sieves PDF Notices of the AMS 43 12 pp 1473 1485 Arjen K Lenstra and H W Lenstra Jr eds The development of the number field sieve Lecture Notes in Math 1993 1554 Springer Verlag Richard Crandall and Carl Pomerance Prime Numbers A Computational Perspective 2001 2nd edition Springer ISBN 0 387 25282 7 Section 6 2 Number field sieve pp 278 301 Datos Q140770Obtenido de https es wikipedia org w index php title Criba general del cuerpo de numeros amp oldid 127108599, wikipedia, wiki, leyendo, leer, libro, biblioteca,
