<p>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.</p>

<p>As for assumptions, pseudorandom generators against poly size circuits <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf">exist</a> if functions computable in deterministic uniform time $2^{O(n)}$ require exponential size circuits. However, complexity zoo's entry for <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aZ#zpp">ZPP</a> points out it's not known whether superpolynomial circuit lower bounds are required to derandomize ZPP.</p>

CC BY-SA 3.0
2011-12-19T13:29:57.007Z
This answer is for polynomial-time algorithms. But the Index Calculus algorithm runs in super-polynomial-time.
Craig Feinstein
CC BY-SA 3.0
2011-12-19T17:42:56.717Z
@Craig Feinstein: You can lift it from polynomial to a larger bound by a simple padding argument.
Emil Jeřábek
CC BY-SA 3.0
2011-12-19T18:31:07.330Z
@CraigFeinstein: yes, what Emil said. The time of the derandomized algorithm will be polynomially related to the expected time of the random algorithm
Sasho Nikolov
CC BY-SA 3.0
2011-12-19T18:34:22.753Z
@SashoNikolov, so you mean that for some polynomial $p$, the time of the derandomized algorithm will be $p(T)$?
Craig Feinstein
CC BY-SA 3.0
2011-12-19T18:35:12.313Z
@EmilJeřábek yes, that makes sense. Thank you.
Craig Feinstein
CC BY-SA 3.0
2011-12-19T22:40:21.230Z
@CraigFeinstein yes
Sasho Nikolov
CC BY-SA 3.0
2011-12-19T02:47:52.563Z
2011-12-19T02:47:52.563Z
Sasho Nikolov
<p>The <a href="http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf" rel="nofollow">Index Calculus Algorithm</a> is a probabilistic algorithm for computing discrete logarithms. Let $T$ be the expected running time of this algorithm. </p>

<p>Suppose that <a href="http://en.wikipedia.org/wiki/Pseudorandom_generator" rel="nofollow">pseudorandom generators exist</a>. 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$?</p>

CC BY-SA 3.0
2011-12-19T02:21:37.007Z
Pseudorandom generators don't generically derandomize randomized algorithms. If they did, we'd have a proof that P = BPP.
Suresh Venkat
CC BY-SA 3.0
2011-12-19T14:11:30.613Z
@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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-19T17:18:19.460Z
true. my point is that the problem is bigger than the OP indicates.
Suresh Venkat
<cc.complexity-theory><derandomization>
Derandomizing the Index Calculus algorithm
Craig Feinstein
# Derandomizing the Index Calculus algorithm

(Asked by: username_0 on 2011-12-18)

The [Index Calculus Algorithm](http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf) is a probabilistic algorithm for computing discrete logarithms. Let $T$ be the expected running time of this algorithm.

Suppose that [pseudorandom generators exist](http://en.wikipedia.org/wiki/Pseudorandom_generator). 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$?

**Tags:** cc.complexity-theory, derandomization

> **Comments:**
> **username_1**: Pseudorandom generators don't generically derandomize randomized algorithms. If they did, we'd have a proof that P = BPP.  
> **username_2**: @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.  
> **username_1**: true. my point is that the problem is bigger than the OP indicates.  

---

## 1 answers

### Answer by username_3 on 2011-12-19. Score: 7 | Accepted answer

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](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf) if functions computable in deterministic uniform time $2^{O(n)}$ require exponential size circuits. However, complexity zoo's entry for [ZPP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aZ#zpp) points out it's not known whether superpolynomial circuit lower bounds are required to derandomize ZPP.

> **Comments:**
> **username_0**: This answer is for polynomial-time algorithms. But the Index Calculus algorithm runs in super-polynomial-time.  
> **username_4**: @username_0: You can lift it from polynomial to a larger bound by a simple padding argument.  
> **username_3**: @CraigFeinstein: yes, what Emil said. The time of the derandomized algorithm will be polynomially related to the expected time of the random algorithm  
> **username_0**: @SashoNikolov, so you mean that for some polynomial $p$, the time of the derandomized algorithm will be $p(T)$?  
> **username_0**: @EmilJeřábek yes, that makes sense. Thank you.  
> **username_3**: @CraigFeinstein yes  

---

