Pollard p-1 分解方法中成功選擇基的機率
在有關 pollard p-1 分解方法的問題中，其中 $ n=pq $ . 我們選擇一些隨機基數 $ a $ , 和一個指數 $ B $ ，希望在哪裡 $ p-1 $ 有小的素因數，如果是這樣，我們希望估計 $ p = \gcd(a^B-1,n) $ .
我們希望估計給定指數的機率 $ B $ , 一個隨機選擇的鹼基 $ a $ 滿足 $ p $ 劃分 $ a^B-1 $ 和 $ q $ 不分 $ a^B-1 $ . 我們假設素數分解 $ p-1,q-1,\text{ and } B $ 是已知的。如何估計成功的機率？謝謝你。
這 $ p-1 $ 根據定義，只要 $ a $ 模組 $ p $ 是一個除數 $ B $ . 如果 $ B $ 是的倍數 $ p-1 $ ，即最大可能的乘法階數 $ a $ ，機率為 $ 1 $ .
那麼，我們關心的情況是 $ B $ 不包含的每個除數 $ p-1 $ . 如果它不包含它們，則機率為 $ 0 $ .
這裡的關鍵挑戰是，擁有一個數字 $ d $ 對應的因素 $ p-1 $ 失踪 $ B $ , 計算元素個數 $ \mathbb{F}_p^{\ast} $ 誰的順序是 $ (p-1)/d $ 或其任何除數。這些元素正是那些從它們的順序中缺失的因子不會影響分解成功的元素。如果 $ d=1 $ ，元素個數為 $ p-1 $ ，即整個範圍。如果 $ d = 2 $ , 這個數字是元素的數量，使得 $ a^{(p-1)/2} = 1 $ ，即二次殘差的模數 $ p $ （不包括 0），恰好是 $ (p-1)/2 $ .
更一般地說，因為 $ \mathbb{F}_p^{\ast} $ 是循環的，每個元素都可以表示為 $ g^e $ , 對於一些原始元素 $ g $ 和一個指數 $ e $ . 我們的目標是計算解決方案的數量 $ e $ 至 $$ g^{e(p-1)/d} = 1 \pmod{p},, $$ 或者換句話說 $$ e(p-1)/d = 0 \pmod{p-1},, $$ 我們可以看到是的倍數 $ d $ 取決於 $ p-1 $ ， IE， $ \frac{p-1}{d} $ .
讓 $ d $ 是因素的乘積 $ p-1 $ 那 $ B $ 不包含，即， $ d = \frac{p-1}{\gcd(p-1, B)} $ . 那麼隨機選擇的順序的機率 $ a $ 分裂 $ n $ 是（誰）給的 $$ \frac{(p-1)/d}{p-1} = \frac{1}{d},. $$
例如，假設 $ p = 15554690395797258751 $ . 現在假設 $ B $ 包含所有因素 $ p-1 = 2\cdot 3 \cdot 5^4 \cdot 11 \cdot 1021 \cdot 25013 \cdot 14765423 $ 除了 $ 2 $ . 那麼機率 $ p-1 $ 分解工作是 $ 1/2 $ . 如果 $ B $ 另一方面太低，不包括 $ 14765423 $ ，這是更可能的情況，分解機率變為 $ 1/14765423 $ .
為了 $ q-1 $ 同樣的考慮也適用。然而，當同時考慮 $ p-1 $ 和 $ q-1 $ 同時，需要減去兩者都成功的情況，在這種情況下也沒有因式分解。如上，假設 $ d_1 $ 失踪了嗎 $ p-1 $ 來自的因素 $ B $ ， 和 $ d_2 $ 那些來自 $ q-1 $ . 那麼我們就有成功的機率 $$ \frac{1}{d_1}\left(1 - \frac{1}{d_2}\right) + \frac{1}{d_2}\left(1 - \frac{1}{d_1}\right) = \frac{1}{d_1} + \frac{1}{d_2} - \frac{2}{d_1d_2},, $$ 那是， $ p-1 $ 成功並且 $ q-1 $ 失敗，或 $ q-1 $ 成功並且 $ p-1 $ 失敗。