# Derandomizing the Index Calculus algorithm

The Index Calculus Algorithm is a probabilistic algorithm for computing discrete logarithms. Let $T$ be the expected running time of this algorithm.

Suppose that pseudorandom generators exist. Does this imply that we could use a pseudorandom generator to derandomize the Index Calculus algorithm and we would have a new deterministic algorithm that solves the Discrete Log problem with a worst-case running-time of $T$?

• Pseudorandom generators don't generically derandomize randomized algorithms. If they did, we'd have a proof that P = BPP. Dec 19, 2011 at 2:21
• @Suresh: In the complexity theory and a certain community in cryptography, “pseudorandom generator” means a pseudorandom generator against poly-size circuits by default, and its existence indeed implies P=BPP. Dec 19, 2011 at 14:11
• true. my point is that the problem is bigger than the OP indicates. Dec 19, 2011 at 17:18

As for assumptions, pseudorandom generators against poly size circuits exist if functions computable in deterministic uniform time $2^{O(n)}$ require exponential size circuits. However, complexity zoo's entry for ZPP points out it's not known whether superpolynomial circuit lower bounds are required to derandomize ZPP.
• @SashoNikolov, so you mean that for some polynomial $p$, the time of the derandomized algorithm will be $p(T)$? Dec 19, 2011 at 18:34