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$?
Derandomizing the Index Calculus algorithm
cc.complexity theory;derandomization
If there exist PRGs that fool polynomial size circuits, then P = BPP, and, since ZPP is in BPP, also ZPP = P. So, any algorithm with expected polynomial running time will have polynomial deterministic running time. However, the running time of the derandomized algorithm will not necessarily be the same as the expected running time of the random algorithm and how they are related will depend on the parameters of the pseudorandom generator. They definitely will be polynomially related.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.