Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

1 Answer 1

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 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 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 at 15:40

Your Answer

 
discard

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.