Если мы можем решить дискретный логарифм с экземплярами $\frac{1}{poly(n)}$, то мы можем с высокой вероятностью решить для всех экземпляров

Я пытаюсь доказать следующее:

Учитывая ансамбль $\{p_n, g_n\}$ ($p_n$ является $n$-bit Prime и $g_n \in \mathbb{Z}^*_{p_n}$ является генератором), если $А$ представляет собой детерминированный алгоритм с полиномиальным временем, такой что:

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

тогда есть алгоритм PPT $А'$ который решает дискретный логарифм с высокой вероятностью для этого ансамбля.

Мне, наверное, нужно как-то позвонить $А$ полиномиальное количество раз и использовать результаты, но у меня нет конкретного направления, как действовать с этой интуицией, чтобы определить $А'$. Очевидно, я могу проверить ответ по $А$, так как вычисление $г^х$ можно сделать за полиномиальное время, а если неправильно - то что?

Обратите внимание, я видел всевозможные вопросы по дискретному журналу, используя что-то, называемое детским шагом, гигантским шагом, но я вообще не знаком с этим (на случай, если это может быть полезно здесь).

Любая помощь будет принята с благодарностью.