The number field sieve's heuristic running time for factoring an -bit number (so ) is…

PHYSICS · Subjective · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch Order finding and Shor's factoring algorithm

Problem

The number field sieve's heuristic running time for factoring an LL-bit number NN (so ln⁡N≈Lln⁡2\ln N \approx L\ln2) is quoted as T∼exp⁡ ⁣[(649)1/3(ln⁡N)1/3(ln⁡ln⁡N)2/3].T \sim \exp\!\left[\left(\frac{64}{9}\right)^{1/3}(\ln N)^{1/3}(\ln\ln N)^{2/3}\right]. For L=2048L=2048 this gives an exponent of about 8181, i.e. T∼e81≈2117T\sim e^{81}\approx2^{117} operations. Estimate the corresponding exponent and the running time, as a power of 22, for L=3072L=3072, an RSA-3072 modulus.

Browse the problem library