在 Pollard p-1 分解方法中使用 a=2 的目的
Pollard p-1 分解方法指出，如果 $ \gcd(2^{B!}-1,n)=p $ 在哪裡 $ p>1 $ 和 $ B $ 界定的主要因素 $ p $ ， 然後 $ p $ 是一個主要因素 $ n $ .
- 難道不應該 $ \gcd(a^{B!}-1,n) $ 對於任何任意 $ a $ ?
- 我們為什麼選擇 $ a=2 $ ? 是因為它的計算能力在計算上更便宜嗎 $ 2 $ ? （ 左移 ）。
- 此外，應 $ B $ 是素因子的上界 $ p-1 $ 或主要因子的上界 $ p-1 $ 連同它的力量？
是的，在波拉德的 $ p-1 $ 我們幾乎可以使用任何 $ a $ 在 $ \gcd(a^{B!}-1,n) $ .
是的，用 $ a=2 $ 因為計算 $ 2 $ ，但在提議的虛擬碼中基本上沒有使用。
這個答案的其餘部分解釋了這是怎麼回事。我不會觸及選擇界限的問題 $ B $ ，因為當我們優化 Pollard 的 $ p-1 $ 我們實際上需要考慮和優化兩個邊界的選擇 $ B_1 $ 和 $ B_2 $ , 併計算 $ \gcd(a-1,n) $ 比顯示的更頻繁，並進行一些其他更改；這很容易成為博士學位的主題。
計算時 $ x\gets a^k\bmod n $ 為了 $ k>0 $ ，從左到右的二進制取冪方法為：
$ x\gets a $
對於每一位 $ k $ 從第二重要到最不重要
如果目前位在 $ k $ 是 $ 0 $ 然後
- $ x \gets x\times x\bmod n $
別的
- $ x \gets x\times x\times a\bmod n $
當我們專注於 $ a=2 $ 並考慮大 $ k $ ，我們可以改進上述算法。讓 $ |n| $ 是位數 $ n $ ， 那是 $ |n|\underset{\text{def}}=\left\lceil\log_2(n+1)\right\rceil $ . 我們可以替換第一個 $ u\approx2,|n| $ 通過將第一步更改為算法中的迭代 $ x $ 至 $ x\gets (1\ll u)\bmod n $ . 而且，獨立地，我們可以將最後一步替換為 $ x\gets((x\times x)\ll1)\bmod n $ .
問題是，問題的算法 9.5 的陳述方式，它只使用 $ a=2 $ 第一步。因此，為了通過上述方法獲得任何節省，我們需要稍微改變算法。這個想法是選擇一個界限 $ B_0\le B $ 這樣 $ k=B_0! $ 是可管理的大，並且在問題的算法中替換初始化步驟 $ a $ 和 $ e $ 經過： $ a\gets 2^k\bmod n $ 由我們改進的模冪算法計算，以及 $ e\gets B_0+1 $ .
這只節省了適度的時間，收益遞減規律 $ B_0 $ 成長。