原根在 Pollard 的 P-1 分解算法中的作用
我最近一直在閱讀有關不同因式分解算法的內容，並且偶然發現了這篇討論 Pollard 的 P-1 算法的論文。在第一頁的腳註中，它指出……
例如，請注意 2^8 = 256 ≡ 1 mod 17，即使 2 與 17 互質且 8 ≠ 0。這裡的要點是，如果 a 是模 q 的本原根，則不會發生這種情況。但是相當多的整數是模 q 的原始根，即使 a 不是原始根，也不能保證我們一定會遇到這種情況，因此選擇不同的 a 應該可以。
但是我有點困惑，不明白它在說什麼。有人可以解釋原始根在 Pollard 的 P-1 分解中的作用嗎？
我將按照文件中的步驟，強調原始根的來源。
讓 $ n $ 是兩個素數的乘積，比如說 $ p $ 和 $ q $ ， 挑選 $ 1<a<n $ , 並選擇一些 $ L $ . 該文件提出了一些選擇的方法 $ L $ . 採取以下步驟：
- 計算 $ d_0=\gcd(a,n) $ .
1.1 如果 $ d_0>1 $ ，我們完成了。
1.2 否則，繼續 2。 2. 計算 $ d_1=\gcd(a^L-1,n) $ .
2.1 如果 $ d_1=1 $ ， 然後 $ p\not\mid a^L-1 $ ， IE $ a^L\not\equiv1\pmod{p} $ . 選擇一個新的 $ L $ 並重複。
2.2 如果 $ 1<d_1<n $ ，我們完成了。
2.3 如果 $ d_1=n $ , 選擇一個新的 $ a $ 並重複。
目標是在情況 2.2 中結束，所以我們可以想知道什麼時候不會。
相反，我們最終可能會使用 2.1。這發生在 $ a^L\not\equiv1\pmod{p} $ ，因此當 $ p-1\not\mid L $ . 正如文件所述，我們實際上想要 $ p-1\mid L $ . 這顯然是一個條件 $ L $ ， 獨立於 $ a $ ，所以我們可以簡單地選擇一個新的 $ L $ 並重新啟動。
最後，我們可能會遇到情況 2.3。如前所述，這發生在
$$ a^k\equiv 1\pmod{q} $$ 在哪裡 $ k=L\pmod{q-1} $ . 為此 $ a $ 這會發生嗎？好吧，如果 $ k=0 $ ，然後它會發生在所有人身上。在這種情況下，我們一直很倒霉，並選擇了一個新的 $ a $ 有幫助的可能性很小。 如果 $ k\neq 0 $ ，那麼這不可能發生在所有人身上 $ a $ 的。請記住，原始根 $ x $ 模組 $ q $ 被定義為非零整數 $ x $ 這樣 $ x^n\neq1\pmod{q} $ 對所有人 $ 0<n<q-1 $ . 換句話說， $ a^k\equiv1\pmod{q} $ 只有當 $ a $ 不是原始根模 $ q $ . 我們可以選擇一個新的 $ a $ ，並希望新的是原根。