Nếu chúng ta có thể giải log rời rạc với các trường hợp $\frac{1}{poly(n)}$, thì chúng ta có thể giải, với xác suất cao, cho tất cả các trường hợp

Tôi đang cố gắng chứng minh những điều sau:

Đưa ra một quần thể $\{p_n, g_n\}$ ($p_n$ là một $n$-bit số nguyên tố và $g_n \in \mathbb{Z}^*_{p_n}$ là một máy phát điện), nếu $A$ là một thuật toán thời gian đa thức xác định sao cho:

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

sau đó có một thuật toán PPT $A'$ giải quyết nhật ký rời rạc với xác suất cao cho tập hợp này.

Tôi có lẽ sẽ cần phải bằng cách nào đó gọi $A$ một số lần đa thức và sử dụng kết quả, nhưng tôi không có hướng cụ thể về cách tiến hành với trực giác này để xác định $A'$. Rõ ràng, tôi có thể xác minh phản hồi bằng cách $A$, kể từ khi tính toán $g^x$ có thể được thực hiện trong thời gian đa thức, nhưng nếu nó sai - thì sao?

Lưu ý, tôi đã thấy tất cả các loại câu hỏi trên nhật ký rời rạc bằng cách sử dụng một thứ gọi là bước khổng lồ của bước bé, nhưng tôi hoàn toàn không quen thuộc với điều đó (trong trường hợp nó có thể hữu ích ở đây).

Mọi sự trợ giúp sẽ rất được trân trọng.