Dacă putem rezolva log discret cu pe $\frac{1}{poly(n)}$ instanțe, atunci putem rezolva, cu mare probabilitate, pentru toate instanțele

Încerc să demonstrez următoarele:

Dat un ansamblu $\{p_n, g_n\}$ ($p_n$ este o $n$-bit prim și $g_n \in \mathbb{Z}^*_{p_n}$ este un generator), dacă $A$ este un algoritm de timp polinom determinist astfel încât:

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

apoi există un algoritm PPT $A'$ care rezolvă log discret cu probabilitate mare pentru acest ansamblu.

Probabil că ar trebui să sun cumva $A$ un număr polinom de ori și folosesc rezultatele, dar nu am o direcție concretă cu privire la cum să procedez cu această intuiție pentru a defini $A'$. Evident, pot verifica răspunsul prin $A$, încă de la calcul $g^x$ se poate face în timp polinomial, dar dacă este greșit - atunci ce?

Rețineți, am văzut tot felul de întrebări pe jurnalul discret folosind ceva numit pas baby step giant, dar nu sunt deloc familiarizat cu asta (în cazul în care poate fi util aici).

Orice ajutor ar fi foarte apreciat.