Modifications to the number field sieve (Q1310453): Difference between revisions

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.