Discrete-Logarithm
Pollard 的 Rho - 構造隨機函式
假設我們的目標是解決離散對數問題 $ \alpha^x=\beta $ 在某個循環群中 $ G=<\alpha> $ . 然後我們正在尋找一個（均勻）隨機的元素序列，形式為 $ \alpha^{a_{i}}\beta^{b_{i}} $ , $ i=0,1,2,… $ 這樣我們就可以呼叫“生日悖論”。Pollard 提出了一個功能，該功能顯然工作得很好，但可以改進。
我的問題涉及波拉德 Rho 的具體實現：如果我們生成整數序列 $ {a_{i}} $ , $ {b_{i}} $ 使用隨機數生成器（來自任何給定的程式語言），這會產生可接受的“隨機性水平”嗎？
我之所以問這個問題是因為我偶然發現了有關 Pollard 的 Rho 的“隨機遊走”的文章，這些文章似乎都相當廣泛；這讓我相信，實現所需的隨機性水平是相當棘手的，而且我生成隨機整數的想法存在缺陷。但是，我似乎找不到它。
如果您按照建議隨機生成組元素，那麼您確實可以呼叫“生日悖論”來及時找到對數 $ O(\sqrt p) $ . 不幸的是，您的儲存要求是相同的，因此對於加密有趣的組訂單，您的方法遠非最佳。
對於（顯然）沒有可利用結構（如橢圓曲線）的組，最快的方法是使用“可區分點”，因為它允許您調整參數以適應可用的儲存。然後存在與您是否只是找到一個離散對數或多個離散對數有關的問題。
話雖如此，我相信任何合理的隨機數生成器都會滿足您的方法。如果生成隨機數的特定方法具有始終不同於正常的性能，那麼這可能具有獨立的數學興趣，值得發表。