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

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ This answer is for polynomial-time algorithms. But the Index Calculus algorithm runs in super-polynomial-time. $\endgroup$
    – Craig Feinstein
    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$
    – Emil Jeřábek
    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$
    – Sasho Nikolov
    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$
    – Craig Feinstein
    Dec 19, 2011 at 18:34
  • $\begingroup$ @EmilJeřábek yes, that makes sense. Thank you. $\endgroup$
    – Craig Feinstein
    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.