知道的好處ppp和qqq在 Blum Blum Shub？
通過了解因式分解，您是否獲得了任何優勢 $ M $ （剛剛知道 $ M $ 本身）在Blum Blum Shub生成器中？
我看到的唯一優勢是能夠計算 $ i $ -th 直接數字，而不是迭代它。這對我來說似乎不是一個很大的收穫。
簡短的回答：知道 $ p $ 和 $ q $ 允許建構更高效的生成器，包括具有隨機訪問的生成器。此外，對於一個對手，至少如果 $ p-1 $ 和 $ q-1 $ 可以分解，這允許找到一個週期，並且至少如果生成器允許隨機訪問超過該週期，則建構一個區分符。
帶著秘密種子 $ x_0 $ ，Blum Blum Shub 生成器計算輸出 $ f(x_i) $ 為了 $ i\ge1 $ ， 在哪裡 $ x_i $ 由重複定義 $ x_{i+1}={x_i}^2\bmod M $ ， 和 $ f() $ 是一些功能
$$ such as extraction of the low bit, or eXclusive-OR or all bits $$， 和 $ M=p\cdot q $ 和 $ p $ 和 $ q $ 大不同的素數 $ p\equiv q\equiv 3\pmod4 $ . 這意味著 $ x_i={x_0}^{(2^i)}\bmod M $ ，但直接評估該表達式是有代價的 $ \mathcal O(i) $ , 等價於直接應用遞推式。
了解因式分解 $ M=p\cdot q $ ，我們可以計算大的輸出 $ i $ 直接有效
$$ in time $\mathcal O(\log(i))$ $$, 通過計算 $ {x_0}^{2^i\bmod(p-1)}\bmod p $ 和 $ {x_0}^{2^i\bmod(q-1)}\bmod q $ ，然後使用中國剩餘定理將它們組合成 $ x_i $ . CRT 也可能會稍微加快生成器使用遞歸的速度，正如我的 mikeaso 指出的那樣，並由 poncho在評論中量化（計算時間最多可以減少 $ 1/4 $ 用教科書乘法算法）。 對手（無法訪問生成器的完整內部狀態）知道因式分解 $ M=p\cdot q $ ，並且還能夠分解 $ p-1 $ 和 $ q-1 $ , 可以計算 $ u=\lambda(p-1) $ 和 $ v=\lambda(q-1) $ 在哪裡 $ \lambda() $ 是Carmichael 的函式[或 $ u=\varphi(p-1) $ 和 $ v=\varphi(q-1) $ 在哪裡 $ \varphi() $ 是歐拉的總函式]，那麼 $ \operatorname{lcm}(u,v) $ 這是 BBS 生成器週期的倍數，因為對於所有 $ x $ , $ x^{(2^u)}\equiv x\pmod p $ 和 $ x^{(2^v)}\equiv x\pmod q $ . 從中建立一個區分器是微不足道的
- 一個BBS黑匣子接受 $ i>0 $ 並返回 index 的輸出 $ i $ 在 BBS 序列中為一些固定的未知隨機種子 $ x $ ;
- 一個隨機的預言機黑盒接受 $ i>0 $ 如果是，則返回隨機輸出 $ i $ 之前沒有送出過，否則返回之前的輸出 $ i $ .
區分者通過送出來工作 $ i=1 $ 和 $ i=\operatorname{lcm}(u,v)+1 $ , 如果答案相同，則投注 BBS，否則投注隨機預言機。
什麼時候
- BBS黑匣子只按順序輸出，
- 或通過模數平方順序進行 $ M $ ,
- 或其他界限 $ i $ 保持渺小，
- 或者是在不知道因式分解的情況下建構的 $ M $ ,
- 或者 $ p-1 $ 或者 $ q-1 $ 很難考慮，
那麼我就沒有表現出一個區分器（但如果可以設計一個區分器就不會那麼驚訝了）。