是否可以確定或估計 Blum-Micali PRG 的周期？
Blum-Micali 是一種加密安全的偽隨機數生成器。
構造（來自維基百科）：
- 讓 $ p $ 是一個奇數素數，並且讓 $ g $ 是一個原始根模 $ p $ .
- 讓 $ x_0 $ 成為一粒種子，讓 $ x_{i+1} = g^{x_i}\ \bmod{\ p} $ .
- 這 $ i $ - 如果算法的輸出為 1 $ x_i < \frac{p-1}{2} $ . 否則輸出為 0。
我玩弄了一些小的值 $ p $ 並且注意到如果有一個固定點就會發生循環，即 $ x_{i+1} = x_i = g^{x_i} $ .
例如當 $ g=3 $ 和 $ p=7 $ （來自維基百科原始根範例），有兩個固定點 $ 3^4 = 4 \bmod 7 $ 和 $ 3^5 = 5 \bmod 7 $ . 這對於 Blum-Micali 發生器來說是有問題的，因為它會循環並重複輸出相同的位。
跟大小有關係嗎 $ p $ 以及基於固定點可能性的時期？
在問題的假設下， $ x\mapsto g^x\bmod p $ 是一個排列 $ \mathbb Z_p^* $ ，它具有隨機性的一些特徵。
如果我們對一組大小進行隨機排列 $ s $ ，從隨機點開始迭代的循環長度 $ l $ 恰好有機率 $ 1/s $ , 與整數無關 $ l $ 和 $ 1\le l\le s $ . 循環有長度 $ l $ 或更少的機率 $ l/s $ .
這形成了一個啟發式論證（很明顯，正如托馬斯在評論中指出的那樣），也許它是 $ \epsilon $ -很少有問題生成器的周期長度遠小於 $ \epsilon,p $ .
然而，這遠不是一個證據，甚至是一個令人信服的論點。特別是，因為 $ x\mapsto g^x\bmod p $ 屬於排列的一個非常小的和特殊的子集 $ \mathbb Z_p^* $ ，該子集具有 $ (p-1)/2 $ 元素出 $ (p-1)! $ 排列。
相比之下，DW 的論點是一個有效的證明，即循環長度太大而無法找到 $ p $ 這樣離散對數問題就很難了。然而，這給出了對周期長度的相當寬鬆的安全估計；也許至少可能 $ 2^{100} $ 為了 $ 2048 $ -位隨機播種 $ p $ ，當上述啟發式論證表明可能至少 $ 2^{2040} $ .
由於 Blum-Micali 在密碼學上是安全的，因此您知道不會有一個短週期（沒有一個短到足以在多項式時間內檢測到），因為短週期會違反密碼安全性。因此，您無需擔心這一點。不值得你花時間擔心它：你不太可能會遇到一個短週期。
也就是說，您為什麼要使用 Blum-Micali？我不會推薦它用於任何實際應用。相反，我會推薦 AES-CTR 之類的東西。