Theoretical Computer Science

# What is worst case complexity of number field sieve?

Given composite $N\in\Bbb N$ general number field sieve is best known factorization algorithm for integer factorization of $N$. It is a randomized algorithm and we get an expected complexity of $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)$ to factor $N$.

I looked for information on worst case complexity on this randomized algorithm. However I am unable to locate information.

(1) What is the worst case complexity of Number field sieve?

(2) Also can randomness be removed here to give a deterministic subexponential algorithm?

## Solution

The number field sieve has never been analyzed rigorously. The complexity that you quote is merely heuristic. The only subexponential algorithm which has been analyzed rigorously is Dixon's factorization algorithm, which is very similar to the quadratic sieve. According to Wikipedia, Dixon's algorithm runs in time $e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$. Dixon's algorithm is randomized.

All (heuristically) known subexponential algorithms require randomization. Dixon's algorithm needs to find integers $x$ such that $x^2 \pmod{n}$ is smooth (can be factored into a product of small primes) and "random", and the number-field sieve has similar but more complicated requirements. The elliptic curve method needs to find an elliptic curve modulo $n$ whose order modulo some factor of $n$ is smooth. In both cases it seems hard to derandomize the algorithms.

The nominal worst-case complexity of all these algorithms is infinity: in the case of the quadratic sieve and the number-field sieve you might always be generating the same $x$, while in the elliptic curve method you may always be generating the same elliptic curve. There are many ways around this, for example running an exponential time algorithm in parallel.

• +1 – Since you touched on ECM too: we know a subexp randomized algorithm to compute $n!r$ in $O(exp(\sqrt{\log n}))$ time using ECM where $r$ is unknown and randomized. Do you have an estimate on how many trials of this algorithm suffices to obtain $n!r$ and $n!s$ where $(r,s)=1$? — Sep 12, 2015 at 07:57
• +1 – I have no idea what $n!r$ is, but generally speaking, when choosing parameters in ECM, we are balancing between the probability $p$ that the curve is smooth enough, and the running time $T$ required to test each curve. Usually the balance point is when $1/p \approx T$. So the expected number of trials should be $O(\exp\sqrt{\log n})$. — Sep 12, 2015 at 08:01
• +0 – $n!$ is factorial of $n$. It is an open problem to get straight line complexity of factorial. We know how to compute $n!r$ where $r$ is unknown in subexp time. If we know two different $n!r$ and $n!s$, we can get $(n!r,n!s)=n!$ in subexp time if $(r,s)=1$. — Sep 12, 2015 at 08:04