# Random Self-Reducibility of the Discrete Logarithm

Section 10.1.2 of Sanjeev Arora and Boaz Barak's Computational Complexity: A Modern Approach defines random self-reducibility and proves hardness of the discrete logarithm by reducing a worst case input to a series of random instances. The proof is rather straight forward, but I am having trouble replicating the final error bound.

In particular, randomized algorithm $$A'$$ is said to run algorithm $$A$$ $$O(\frac{1}{\delta \log \frac{1}{\epsilon}})$$ times. $$A$$ succeeds with probability $$\delta$$, so one possible bound of the error probability of $$A'$$ should be

$$\mathbb{P}[A' \text{ fails }] = (1 - \delta)^{\frac{1}{\delta \log\frac{1}{\epsilon}}} \leq (e^{-\delta})^{\frac{1}{\delta \log\frac{1}{\epsilon}}} = e^{\frac{1}{\log \epsilon}} \neq \epsilon$$

Arora and Barak are able to achieve the bound $$\mathbb{P}[A' \text{ fails }] \leq \epsilon$$, but it seems my attempts have resulted in loose bounds. I'd love some direction as to how I could potentially reach the tighter bound that the textbook achieves.

Alternatively, because the book is a draft, it is possible this is a typo. With $$O(\frac{\log \frac{1}{\epsilon}}{\delta})$$ runs of $$A$$, my simple technique above is able to reach the $$\epsilon$$ bound.

• Yes, that's a typo. Nov 8, 2022 at 23:37
• Agreed, for example for $\delta \approx 1$ it says to run it $o(1)$ times as $\epsilon\to 0$. That makes no sense. Nov 9, 2022 at 3:08