# Time complexity to solve Discrete log problem

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

## 1 Answer

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

• 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