在以 p 為模的乘法群中找到四分法

我有一個關於離散對數問題的變體，涉及在整數的乘法循環群中以大素數為模找到四分法 $ p $ :

$$ a = x^x \mod p $$

在哪裡 $ a $ 和 $ p $ 是已知的，並且 $ p $ 不一定是安全的素數。能 $ x $ 有效地找到還是至少和 DLP 一樣難？

正如評論中所指出的，問題出在哪裡還不是很清楚，但這裡有一個簡單的算法，可以用於（可以說）最自然的解釋。

給定任何素數 $ p $ 和整數 $ a $ ，下面的過程找到一個整數 $ x\in\mathbb Z_{\geq0} $ 這樣 $$ x^x\equiv a\pmod p ,\text. $$

---

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 $ .

引用自：https://crypto.stackexchange.com/questions/72803