Strengthening a given attack on discrete log
Suppose that we had a stronger guarantee: $A'$ is a randomized algorithm, and for every $b$, $\Pr[A'(b) = \log_g b] &gt; 1/2$, over the randomness of the algorithm. In that case, you would construct $A$ by running $A'$ several times, and checking each output until you get one that satisfies $g^{A'(b)} = b$.
Now suppose that the guarantee is $\Pr_b[A'(b) = \log_g b] &gt; 1/2$. You would like to somehow get &quot;independent samples&quot; of $A'(b)$. You can accomplish that using randomized self-reducibility. I'll let you fill that out since it's your exercise. The resulting algorithm is randomized, but by choosing the optimal randomness, you get a deterministic (but non-uniform) algorithm with the same guarantees.