Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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})$.

share|improve this question
up vote 2 down vote accepted

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}} $$

share|improve this answer
Note that this is a heuristic asymptotic complexity, not a proven one. – Reid Jan 13 '14 at 20:42
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. – Samuel Neves Jan 13 '14 at 20:45
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$. – fgrieu Jan 14 '14 at 15:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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