Metraipolis › archive › dc_cd356d8f8d5e
General number field sieve — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/General_number_field_sieve
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-15T14:00:44.775Z
- SHA-256 of the archived text
b89f2e7d6570005a29ec3094656a8d5fe63014f5325b9b3a4aebde62c9ff53ae- Stable URL of this page
https://metraipolis.com/documento/dc_cd356d8f8d5e
How to cite
General number field sieve — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/General_number_field_sieve (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_cd356d8f8d5e (Metraipolis archive dc_cd356d8f8d5e, sha256 b89f2e7d6570005a29ec3094656a8d5fe63014f5325b9b3a4aebde62c9ff53ae)
BibTeX
@misc{dccd356d8f8d5e,
title = {General number field sieve — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/General_number_field_sieve},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_cd356d8f8d5e; sha256 b89f2e7d6570005a29ec3094656a8d5fe63014f5325b9b3a4aebde62c9ff53ae},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/General_number_field_sieve. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 10100. Heuristically, its complexity for factoring an integer n {\displaystyle n} (consisting of ⌊ log 2 n ⌋ + 1 {\displaystyle \left\lfloor \log _{2}n\right\rfloor +1} bits) is of the form exp ( ( ( 64 / 9 ) 1 / 3 + o ( 1 ) ) ( log n ) 1 / 3 ( log log n ) 2 / 3 ) = L n [ 1 / 3 , ( 64 / 9 ) 1 / 3 ] {\displaystyle {\begin{aligned}&\exp \left(\left((64/9)^{1/3}+o(1)\right)\left(\log n\right)^{1/3}\left(\log \log n\right)^{2/3}\right)\\[5pt]={}&L_{n}\left[1/3,(64/9)^{1/3}\right]\end{aligned}}} in Big-O and L-notations. It is a generalization of the special number field sieve: while the latter can only factor numbers of a certain special form (including numbers of the form a b n + c {\displaystyle ab^{n}+c} with small a {\displaystyle a} and small c {\displaystyle c} , and Fibonacci numbers and Lucas numbers, but not n ! ± 1 {\displaystyle n!\pm 1} or p # ± 1 {\displaystyle p\#\pm 1} ), the general number field sieve can factor any number apart from prime powers (which are trivial to factor by taking roots). The principle of the number field sieve (both special and general) can be understood as an improvement to the simpler rational sieve or quadratic sieve. When using such algorithms to factor a large number n {\displaystyle n} , it is necessary to search for smooth numbers (i.e. numbers with small prime factors) of order n {\displaystyle {\sqrt {n}}} . The size of these values is exponential in the size of n {\displaystyle n} (see below). The general number field sieve, on the other hand, manages to search for smooth numbers that are subexponential in the size of n {\displaystyle n} . Since these numbers are smaller, they are more likely to be smooth than the numbers inspected in previous algorithms. This is the key to the efficiency of the number field sieve. In order to achieve this speed-up, the number field sieve has to perform computations and factorizations in number fields. This results in many rather complicated aspects of the algorithm, as compared to the simpler rational sieve. The size of the input to the algorithm is log 2 n {\displaystyle \log _{2}n} or the number of bits in the binary representation of n {\displaystyle n} . Any element of the order n α {\displaystyle n^{\alpha }} for a constant α {\displaystyle \alpha } is exponential in log n {\displaystyle \log n} . The running time of the number field sieve is super-polynomial, but sub-exponential in the size of the input.
Tema degli esploratori: calcolo e infrastrutture (deposito sistematico; ricerca «volunteer computing»).
Fonte: Wikipedia in inglese, voce «General number field sieve» — https://en.wikipedia.org/wiki/General_number_field_sieve
Wikidata Q140770 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q140770
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/General_number_field_sieve?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 1377718368, consultata il 2026-10-15T13:50:23.322Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 286ab4f2dbb7350919a10ee3b201b6e40867749824b796a3890c4966f791165f