Theoretical Computer Science
- reference-request derandomization factoring average-case-complexity worst-case
- Updated Wed, 22 Jun 2022 18:15:23 GMT
-
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.
Comments (5)
- +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
- +0 – I remember calculating a while back. I do not think I could get an improvement since there was a catch and I do not remember the details. — Sep 12, 2015 at 08:15
- +0 – the last paragraph seems strange & could be clarified more. are you talking about a scenario where the RNG is "broken" in the sense it doesnt sample the overall distribution space? but then wouldnt parallelism not help there? because it would be the same "broken" RNG in parallel? or is the idea it would be a different RNG run in parallel? actually parallel complexity of factoring algorithms is really a whole other complex topic eg some can be parallelized better than others, big-O might not exactly be applicable, etc — Sep 12, 2015 at 15:11