问乘法群模p中的求取方法

EN

正如评论中指出的那样，问题是什么还不太清楚，但这里有一个简单的算法，用于(可以说)最自然的解释。

给定任何素数p和整数a，下面的过程找到一个整数x\in\mathbb Z_{\geq0}，以便

1. 选择一些正整数的e副本到p-1。(例如，e=1总是工作的。)
2. 用x=e+k(p{-}1)和k\in\mathbb Z_{\geq0}编写预期的解决方案。
3. 由于x的阶数必须是p-1的除数，所以方程变为(e+k(p{-}1))^{e}\bmod p=a \,\text. ，将一切都提高到f:=e^{-1}\bmod(p{-}1)的幂，从而得到e+k(p{-}1) \equiv a^f \pmod p \,\text. 。
4. 只需为k求解此同余，即计算k := (e-a^f)\bmod p \,\text. 。
5. 输出x:=e+k(p{-}1)。

请注意，x的预期大小约为p^2。