-1
$\begingroup$

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$?

$\endgroup$
3
  • 2
    $\begingroup$ Pseudorandom generators don't generically derandomize randomized algorithms. If they did, we'd have a proof that P = BPP. $\endgroup$ Dec 19, 2011 at 2:21
  • 3
    $\begingroup$ @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. $\endgroup$ Dec 19, 2011 at 14:11
  • 2
    $\begingroup$ true. my point is that the problem is bigger than the OP indicates. $\endgroup$ Dec 19, 2011 at 17:18

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ This answer is for polynomial-time algorithms. But the Index Calculus algorithm runs in super-polynomial-time. $\endgroup$ Dec 19, 2011 at 13:29
  • 3
    $\begingroup$ @Craig Feinstein: You can lift it from polynomial to a larger bound by a simple padding argument. $\endgroup$ Dec 19, 2011 at 17:42
  • $\begingroup$ @CraigFeinstein: yes, what Emil said. The time of the derandomized algorithm will be polynomially related to the expected time of the random algorithm $\endgroup$ Dec 19, 2011 at 18:31
  • $\begingroup$ @SashoNikolov, so you mean that for some polynomial $p$, the time of the derandomized algorithm will be $p(T)$? $\endgroup$ Dec 19, 2011 at 18:34
  • $\begingroup$ @EmilJeřábek yes, that makes sense. Thank you. $\endgroup$ Dec 19, 2011 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.