IIS quiz q1b.md

If $p-1$ can be written as $(p-1) = s2^r$ where $s$ is odd, then the $(r+1)$th LSB of x ( the discrete log) is a hardcore predicate for the discrete log problem. Using this fact, design a pseudorandom generator.

Overall Proof: if DLP $\lt_p$ DLP-(r+1)LSB, then DLP-(r+1)th LSB is as computationally hard as DLP. Since DLP itself is one way function, DLP(r+1)th LSB must be a hardcore predicate of DLP.

Consider the following algorithm to find x satisfying $g^x = y$, given access to the $(r+1)^th$ bit:

Algorithm $$ y_0 \to y asdf asd

$$