為離散對數實施 Pollard 的 Rho 問題
我最近一直在嘗試實施 Pollard 的 Rho。最初的想法是用多種語言實現程式碼，並出於教育目的將其發布給大家。我首先訪問了 Wikipedia，並實現了Pollard 的 rho algorithm for logarithms中的程式碼。我將程式碼直接從 C++ 翻譯成Haskell，它生成了與 C++ 相同的輸出，所以我很高興。它同意維基百科頁面中的範例。但是，在獲取輸出和求解時 $ (B - b)\ \gamma \equiv (a - A)\pmod n $ ，我得到的結果與對數應該不同。如果您想對此程式碼發表評論，請評論維基百科文章中的 C++ 程式碼，我想這是最容易訪問的版本。
對 Wikipedia 文章不滿意，我進一步搜尋並找到了一個基於應用密碼學手冊中的算法 3.60 的Python 程式碼的要點，連結在要點中。這個版本可以計算程式碼中提到的例子的對數（取自書中）。它對來自維基百科頁面的程式碼產生不同的結果。我已經驗證過了，Python 程式碼讀起來和書中描述的算法完全一樣。但是，如果我餵牠像 $ n=6,\ Z=7,\ alpha=5,\ beta=4 $ 那麼顯然 $ dlog $ 的 $ 4 $ 到基礎 $ 5 $ 在 $ \mathbb{Z}7^* $ 應該 $ 2 $ ， 因為 $ 5^2\pmod 7 \equiv 25\pmod 7 \equiv 4 \pmod 7 $ . 但相反，它會因異常而崩潰，因為它試圖獲得 $ 4\pmod 6 $ ，顯然沒有，因為 $ gcd(4, 6) = 2 \neq 1 $ . 這樣做是因為在算法的最後一步，如列印頁 106 所述，它將到達 $ r = b_i - b{2i} = 4 $ 它必須計算 $ r^{-1} $ . HAC 應該是一本受人尊敬的書，但我的程式碼產生了不好的結果，所以我做錯了什麼嗎？書錯了嗎？
我現在已經花了幾天時間。是的，我已經通讀了這個堆棧交換來尋找 Pollard 的 Rho。如何修復此程式碼？為什麼 Python 和 C++ 程式碼會崩潰？是否有一個版本的 Pollard 的 Rho 算法通常只適用於少數特定情況？有沒有描述這種算法的書？有人可以指出我的工作版本嗎？
首先，Pollard Rho 找到了一個本質上隨機的解 $ (B - b) \gamma \equiv (a - A) \pmod{N} $ . 這種隨機性意味著如果 $ N $ 有一個主要因素 $ p $ ， 然後 $ B - b $ 有機率 $ 1/p $ 具有 $ p $ 作為倍數（因此它將以您所看到的方式失敗）。
Pollard Rho 通常與 $ N $ 是一個大素數；唯一的主要因素 $ N $ 事實上，有 $ N $ ，所以它有一個微小的變化（ $ 1/N $ ) 的失敗。當然，您將它與玩具參數一起使用，因此失敗的可能性要高得多。
這確實很重要。在群裡 $ Z_p^* $ , $ N = p-1 $ 總是均勻的；這不是意味著 Pollard-Rho 總是有 50% 的失敗機率嗎？
好吧，如果我們以直接的方式使用它，它會的。但是，我們所做的是在素數子域（或者，至少是一個沒有小因子的子域）中執行操作；這使得故障機率很小。
如果我們確實必須在一個包含小因素的小組中做這項工作，比如說， $ N = hq $ ， 在哪裡 $ h $ 是光滑的，並且 $ q $ 沒有小因素，那麼我們能做的就是計算 $ a^h $ 和 $ b^h $ , 並使用 Pollards-Rho 計算 $ \gamma’ $ 這樣 $ (a^h)^{\gamma’} \equiv (b^h) $ ; 這是在 $ q $ 大小的子組，因此具有很高的成功機率。給定 $ \gamma’ $ , 很容易重構 $ \gamma $ ， 作為 $ \gamma \equiv \gamma’ \pmod q $