New answers tagged

3 votes
Accepted

If we can solve discrete log with on $\frac{1}{poly(n)}$ instances, then we can solve, with high probability, for all instances

Yes, the discrete logarithm is random self reduceable, that is the worst case is as hard as the random case. If we are given y and wish to find $x$ s.t $y=g^x \bmod p$ we can pick a random a and ...
user avatar
  • 10.4k

Top 50 recent answers are included