
doi: 10.1007/bf00198464
The number field sieve, due to Lenstra et al. and Buhler et al., is a routine for factoring integers. The running time of this algorithm is estimated at \(e^{1.923+ \sigma(1) (\log N)^{1/3} (\log\log N)^{2/3}}\), where \(N\) is the number to be factored and \(\sigma(1)\) tends to 0 as \(N\to\infty\). The paper gives a brief description of the sieve method and describes a modification which reuses the computations of the initial sieve to reduce the exponent in the running time expression from 1.923 to 1.902. Furthermore, the same ideas are used to describe a way to precompute tables which are useful in factoring any integers in a large range. Ignoring the cost of the precomputations, an individual integer can be factored in time \(e^{1.639+ \sigma(1) (\log N)^{1/3} (\log\log N)^{2/3}}\). This substantial decrease in the time for factoring integers could have implications for the choice of prime parameters in cryptography.
cryptography, factorization of integers, factoring algorithm, Cryptography, number field sieve, Factorization, Number-theoretic algorithms; complexity
cryptography, factorization of integers, factoring algorithm, Cryptography, number field sieve, Factorization, Number-theoretic algorithms; complexity
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 54 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
