# If we can solve discrete log with on $\frac{1}{poly(n)}$ instances, then we can solve, with high probability, for all instances

I am trying to prove the following:

Given an ensemble $$\{p_n, g_n\}$$ ($$p_n$$ is an $$n$$-bit prime and $$g_n \in \mathbb{Z}^*_{p_n}$$ is a generator), if $$A$$ is a deterministic polynomial time algorithm such that:

$$\Pr_{x \leftarrow \mathbb{Z}^*_{p_n}} [A(a)=x \text{ where } g_n^x=a]=\frac{1}{poly(n)}$$

then there is a PPT algorithm $$A'$$ that solves discrete log with high probability for this ensemble.

I would probably need to somehow call $$A$$ a polynomial number of times and use the results, but I have no concrete direction on how to proceed with this intuition to define $$A'$$. Obviously, I can verify the response by $$A$$, since computing $$g^x$$ can be done in polynomial time, but if it's wrong - then what?

Note, I have seen all sorts of questions on discrete log using something called baby step giant step, but I am not familiar with that at all (in case it may be useful here).

Any help would be greatly appreciated.

If we are given y and wish to find $$x$$ s.t $$y=g^x \bmod p$$ we can pick a random a and calculate b=$$g^a\times y =g^{a+x}$$
This value $$b$$ is uniformly distributed regardless of y. If however, we solve a discrete logarithm for it we can easily subtract $$a$$ and find $$x$$.