What is the time to complexity to solve Discrete log problem now in $Z_p$?

Initially for $n$ bit prime $p$, it was $Exp(n^{1/3})$.


These days the fastest general method to solve discrete logarithms modulo primes is the number field sieve, which has the asymptotic complexity

$$ e^{(1.92+o(1)) (\log p)^{1/3} (\log\log p)^{2/3}} $$

  • $\begingroup$ Note that this is a heuristic asymptotic complexity, not a proven one. $\endgroup$
    – Reid
    Jan 13 '14 at 20:42
  • $\begingroup$ You're right, of course. Given it's little-oh, that factor can actually be any function, as long as it becomes insignificant at infinity input sizes. $\endgroup$ Jan 13 '14 at 20:45
  • $\begingroup$ Thanks for fixing the formula (save for the dots after 1.92). Notice that the little-oh in the exponent makes it impossible to give a big-Oh expression for the complexity. If that $o(1)$ is taken to be $0.01$, the effort is raised by $37\%$ for $1024$-bit $p$, and $52\%$ for $2048$-bit $p$. $\endgroup$
    – fgrieu
    Jan 14 '14 at 15:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.