Self-DLOG 有多難？
這個問題在要求不同的東西時提出了一個有趣的問題：如果你能找到 $ x $ 這樣 $ x\equiv R^x\pmod p $ 那麼你可以打破DSA。現在我認為人們可能能夠以某種方式將其與離散對數問題聯繫起來，但我沒有找到這種關係，所以我問了這個（更一般的）問題。
現在我的問題是：
讓 $ p $ 是任意素數，是否存在比 $ \mathcal O(p) $ 其中，給定 $ p $ 和任意 $ R\in\mathbb Z $ , 找到一個 $ x\in{y\in\mathbb Z\mid 0\leq y<p} $ 這樣 $ x\equiv R^x\pmod p $ 如果這樣一個 $ x $ 存在或 $ \perp $ 否則？
關於離散對數不動點的問題稱為Brizolis 問題。特別是對於解決方案的平均數量
$$ N(p)=\frac{1}{\varphi(p-1)}\sum_g\left|{0\le x\le p-1:g^x=x\pmod p}\right| $$眾所周知 (Grechnikov, 2012) $ N(p)=1+S(p) $ ， 在哪裡 $$ -C(\varepsilon)p^{-1/4+\varepsilon}\le S(p)\le \exp(C’\mathrm{Li}((\log p)^{c\frac{\log\log\log\log p}{\log\log\log p}})). $$ 還有必要說逆問題更容易：對於給定的 $ x $ 一個可以拿 $ R=x^{x^{-1}\bmod (p-1)}. $
這樣的點就是我們所說的函式的“不動點” $ f(x) = g^x $ . 在談論找到這樣一個點之前，需要問這樣一個問題是否存在。我向您推薦 Levin、Pomerance 和 Soundararajan 的論文Fixed Points for Discrete Logarithms，該論文研究了這個確切的問題（他們也有一個算法，但我沒有嘗試計算它的複雜性；我將把它留給你）。