Metraipolis › archive › dc_518ed2fa3693
Criba general del cuerpo de números — Wikipedia (es)
- Source
- Wikipedia (es)
- Original
- https://es.wikipedia.org/wiki/Criba_general_del_cuerpo_de_n%C3%BAmeros
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T11:22:24.241Z
- SHA-256 of the archived text
43f518ad4c2d1390b6b830a9ee41cfc52c0408100c41eaf7742f2ca57be490fc- Stable URL of this page
https://metraipolis.com/documento/dc_518ed2fa3693
How to cite
Criba general del cuerpo de números — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Criba_general_del_cuerpo_de_n%C3%BAmeros (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_518ed2fa3693 (Metraipolis archive dc_518ed2fa3693, sha256 43f518ad4c2d1390b6b830a9ee41cfc52c0408100c41eaf7742f2ca57be490fc)
BibTeX
@misc{dc518ed2fa3693,
title = {Criba general del cuerpo de números — Wikipedia (es)},
howpublished = {Wikipedia (es)},
url = {https://es.wikipedia.org/wiki/Criba_general_del_cuerpo_de_n%C3%BAmeros},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_518ed2fa3693; sha256 43f518ad4c2d1390b6b830a9ee41cfc52c0408100c41eaf7742f2ca57be490fc},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Criba_general_del_cuerpo_de_n%C3%BAmeros. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En teoría de números, la criba general del cuerpo de números (del inglés general number field sieve (GNFS) es el algoritmo clásico conocido más eficiente para factorizar enteros mayores de 100 dígitos. Heurísticamente, 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 notación L), donde ln es el logaritmo en base e. 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 log2 n 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.
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoría de números»).
Fonte: Wikipedia in spagnolo, voce «Criba general del cuerpo de números» — https://es.wikipedia.org/wiki/Criba_general_del_cuerpo_de_n%C3%BAmeros
Wikidata Q140770 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q140770
Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Criba_general_del_cuerpo_de_n%C3%BAmeros?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 146700682, consultata il 2026-10-07T11:15:27.867Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 4f0af93b5662ac82e1df85df260843a771d1c93137ccf0a05445296127d156a2