Factoring
為什麼在 Pollard 中使用階乘p-1p−1p - 1算法？
為什麼我們要使用階乘來尋找 $ L $ 可以被 $ p - 1 $ ?
Pollard 的算法是關於 B-powersmooth 數而不是 B-smooth 數。那麼階乘到底是從哪裡來的呢？階乘不是通過為任何東西提供動力來完成的——它只是數字的乘法，沒有任何指數。
我指的是波拉德的 $ p - 1 $ Silverman 的數學密碼學書中介紹的算法 - 他們檢查的地方 $ a^{j!} - 1 $ 在一個循環中（隨著 j 遞增）直到他們找到正確的 $ gcd(a^{j!} - 1) $ 這導致了一個因素。
我理解使用費馬小定理來證明 L 是這樣的部分 $ p-1 $ 劃分 $ a^L - 1 $ & $ q-1 $ 不分 $ a^L - 1 $ - 我的問題與此無關。我的問題是為什麼/如何嘗試 $ {j!} $ （即嘗試階乘）尋找合適的 $ L $ ?
費馬定理 位於第二個因式分解方案的背後，稱為 pollard p-1 方法。
- 假設要分解的奇數複合整數 n 具有素數除數 n，其性質是 p-1 是相對較小素數的乘積。令 q 為滿足 (p-1)|q 的任意整數。例如 q 可以是 k! 或前 k 個正整數的最小公倍數，其中 k 取足夠大。選擇 1<a<p-1
- $$ {m\equiv a^q \equiv a^{(p-1)j}\equiv 1^j \equiv1(modp)} $$暗示 p | (m-1)，這力量 $ {gcd(m-1,n)>1} $
- 但重要的是這裡要注意的是，如果 $ {gcd(m-1,n)=1} $ ，那麼應該返回並選擇 a 的不同值。
- 如果 q (k!) 不夠大，該方法可能會失敗；也就是說，如果 p-1 包含大素數因子或小素數出現大冪，因此最好選擇 k!，而不是每次得到時都猜測任何新的大數 $ {gcd(m-1,n)=1} $ ，因此階乘是更好的選擇，並且可以增加發現一個因子是否為大素因子的機率。