14
$\begingroup$

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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ 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$? $\endgroup$
    – user34945
    Sep 12, 2015 at 7:57
  • 1
    $\begingroup$ 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})$. $\endgroup$
    – Yuval Filmus
    Sep 12, 2015 at 8:01
  • $\begingroup$ $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$. $\endgroup$
    – user34945
    Sep 12, 2015 at 8:04
  • $\begingroup$ 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. $\endgroup$
    – user34945
    Sep 12, 2015 at 8:15
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Sep 12, 2015 at 15:11
8
$\begingroup$

In the past few months, a version of the number field sieve has been analyzed rigorously: http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring

Basically the worst-case running time is $L_n(1/3, 2.77)$ unconditionally and $L_n(1/3, (64/9)^{1/3})$ under GRH. This is not for the "classic" number field sieve, but a slightly modified version which randomizes more steps in order to make the complexity analysis easier.

I believe the corresponding paper is still under review.

Update: The paper is out now. Jonathan D. Lee and Ramarathnam Venkatesan, "Rigorous analysis of a randomised number field sieve," Journal of Number Theory 187 (2018), pp. 92-159, doi:10.1016/j.jnt.2017.10.019

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Can you give a more complete reference where we can learn more, with title, author, and where published, so that the answer is still useful even if the link stops working? $\endgroup$
    – D.W.
    Sep 18, 2016 at 2:38
  • $\begingroup$ Since the result was only recently announced, I believe it is currently under review as indicated in my answer, and therefore not yet published. I will update my answer in the future when publication information is available. $\endgroup$
    – djao
    Sep 18, 2016 at 21:55
  • $\begingroup$ FWIW it doesn't seem to be on arxiv.org. However, the author is Ramarathnam Venkatesan, which may help future searches should they be necessary. $\endgroup$
    – Peter Taylor
    Sep 19, 2016 at 8:23
  • $\begingroup$ It is actually a two-author work (J. D. Lee and R. Venkatesan) : cmi.ac.in/activities/… $\endgroup$
    – Sary
    Nov 21, 2016 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy