Strengthening a given attack on discrete log I am trying to prove the following claim:

Let $(G,*)$ be a cyclic group of size $m$ with generator $g$. Assume
there exists some adversary $A'$ of size
$T'=\frac{\left(T-O\left(\log m\right)\right)}{2}$, for some
$T$, such that $$\mathbb{P}_{b\gets
 G}\left[A'(b)=\log_{g}(b)\right]&gt;\frac{1}{2}.$$ Show that there exists
an adversary $A$ of size $T$ such that $$\mathbb{P}_{b\gets
 G}\left[A(b)=\log_{g}(b)\right]&gt;\frac{3}{4}.$$
Assume multiplication over $G$ requires $O(1)$ circuit.

How can I prove this claim? Intuitively, since $A$ is bigger than $A'$ in about $O(\log m)$, the construction should be based on dividing the problem into halfs recursively, as in binary search. However, I can't think of any clever way to do that...
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.