Hardcore Bit proof for discrete log I am studying Crypto and am trying to understand why discrete log creates is useful for creating a PRG. More specifically, I want to prove via reduction that  $B(x)=(x&lt;p/2)$ is a hardcore bit for the one-way function $f_{p,g}(x)=g^x \bmod p$. So far, I have shown that if there is a polynomial-time algorithm $D$ that computes this bit perfectly, then
there is another polynomial-time algorithm $I$ that inverts the one-way function perfectly. 
I want to extend the proof to the case
when $D$ is imperfect, but successful with probability $\frac12 +\epsilon$ for some nonnegligible $\epsilon$
(in this case, the probability is taken over a random choice of $x$ between 0 and $p-1$). I want to show that for this case,
it is possible to invert $f$ with nonnegligible probability in polynomial time.

Any help is appreciated.
The usual approach is to identify a randomized self-reduction.  In other words, given a problem instance $x$, you generate a randomized version of $x$, say $x'$, and show how the solution to $x'$ gives you the solution to $x$.

How does this help?  Given a problem instance $x$, you can generate many randomized versions, say $x'_1,x'_2,\dots,x'_m$ (each one using independent randomness).  Now, try to solve each of the $x'_1,x'_2,\dots,x'_m$.  By the conditions of your problem, you know that you'll have a way to solve them, so that a $1/2 + \epsilon$ fraction of the answers are correct: i.e., so that $m/2 + \epsilon m$ of the $m$ answers are correct.

Now, you take it from here.  How could you use that to form a reasonable guess at the solution to $x$?