Let g generate a group G of size q $($say in Z$\backslash$times p$)$ and consider the discrete logarithm

problem in G$.$ Suppose there exists A in PPT such thatPrx$$Zq$[$A$($gx$)=$ x$]=.$

That is$,$ A succeeds with probability $$ on random instances of the DLP in G$.$ Show

that this implies the existence of another efficient algorithm A$$ which runs in expected

polynomial time in $1/$ and solves any instance in G with probability $1.($Hint: Since A

is only guaranteed to work on random instances, you need to find a way to randomize

the instance your A$$ is given so that a solution from A will still help you.$)$