估計 Pollard 的 p-1 的成功機率
我試圖估計Pollard 的 p-1 分解在其兩階段變體中找到 RSA 模乘積的一個因子的機率 $ k $ 隨機的 $ b $ 位素數，作為邊界的函式 $ B_1 $ 和 $ B_2 $ 用過。
那是關於 $ 1-(1-P)^k $ ，或大約 $ k,P $ 對於低 $ P $ ， 在哪裡 $ P $ 是一個機率 $ b $ 位素數 $ p $ 有 $ p-1 $ 其最大質因數小於 $ B_2 $ 並且它的第二大素因數小於 $ B_1 $ .
我的（不正確的）想法是我們必須有 $ P\ge\rho\Bigl(\frac{b-1}{\log_2(B_2)}\Bigr)\rho\Bigl(\frac{\log_2(B_2)}{\log_2(B_1)}\Bigr) $ 在哪裡 $ \rho $ 是迪克曼函式 $$ * $$, 假設 $ p-1 $ 表現得像一個隨機偶數，即最大素因子的機率 $ q $ 小於 $ B_2 $ 是關於 $ \rho\Bigl(\frac{b-1}{\log_2(B_2)}\Bigr) $ ; 然後第二大素因子的條件機率小於 $ B_1 $ 是關於 $ \rho\Bigl(\frac{\log_2(q)}{\log_2(B_1)}\Bigr) $ ，這至少是 $ \rho\Bigl(\frac{\log_2(B_2)}{\log_2(B_1)}\Bigr) $ .
問題是，我的估計比gmp-ecm給出的選項要大得多
-pm1 15e9$$ # $$它估計自己的成功機率為：
Using B1=15000000000, B2=19849281594647716 (..) Probability of finding a factor of n digits (assuming one exists): 20 25 30 35 40 45 50 55 60 65 0.84 0.58 0.32 0.15 0.063 0.023 0.0078 0.0024 0.00068 0.00018為了 $ n=65 $ 十進制數字，即 $ b=216 $ ，我得到 $ P $ 至少 $ 0.0028 $ ，這是 ECM 估計的 15 倍以上 $ 0.00018 $ .
造成這種差異的原因是什麼？
$$ * $$ 迪克曼函式 $ \rho $ 被定義為 $ u\in\mathbb R^+ $ 經過 $$ \begin{cases} \rho(u)=1 & \text{if }0\le u\le1\ \rho(u)=1-\int_1^u\rho(t-1)/t;dt& \text{if }u>1 \end{cases} $$ 作為 $ B $ 增長，一個隨機整數的機率大約 $ B^u $ 其所有質因數小於 $ B $ 收斂到 $ \rho(u) $ . 有時它被認為是迪克曼的功能 $ F $ 被定義為 $ F(\alpha)=\rho(1/\alpha) $ . 特別是，Richard P. Brent 的Some Integer Factorization Algorithms using Elliptic Curves使用 $ \rho $ 為了那個原因 $ F $ .
$$ # $$ 帶有選項的 gmp-ecm在ANTS 2008的程序中
-pm1實現了 Peter L. Montgomery 和 Alexander Kruppa改進的第 2 階段到 P±1 因子算法。第一個參數是 $ B_1 $ . $ B_2 $ 如果未指定為第二個參數，則自動選擇。
估計 Pollard 的 p-1 分解在其兩階段變體中找到 RSA 模乘積的因子的機率 $ k $ 隨機的 $ b $ 位素數，作為邊界的函式 $ B_1 $ 和 $ B_2 $ 用過的
TLDR：GMP-ECM 很好。修改它為 $ b $ 位而不是
n十進制數字，並使用 $ k;P $ 在哪裡 $ P $ 是顯示的低機率。GMP-ECM 的計算
ecm -v -pm1方式 $ P $ Alexander Kruppa 在他的博士論文第 5.3.3 節中將其描述為 $$ P=\hat\rho\biggl(\frac{\log(N_\text{eff})}{\log(B_1)},N_\text{eff}\biggr)+\sum_{B_1<q\le B_2\\quad q\in\Bbb P}\hat\rho\biggl(\frac{\log(N_\text{eff}/q)}{\log(B_1)},N_\text{eff}/q\biggr)/q $$ 在哪裡 $$ \begin{align}\hat\rho(u,x)&=\rho(u)-\gamma\frac{\rho(u-1)}{\log(x)}\ \gamma&=\lim_{n\to\infty}\biggl(-\log(n)+\sum_{i=1}^n\frac 1 n\biggr) \approx0.5772156649\ N_\text{eff}&=N;e^{-\delta}\ \delta&=\sum_{q\in\Bbb P}\frac{\log(q)}{(q-1)^2}\approx1.2269688057\ N&=2^{b-0.5}\text{ is an approximation of the factor} \end{align} $$在這， $ \displaystyle\hat\rho\biggl(\frac{\log(N)}{\log(B_1)},N\biggr) $ 估計隨機整數附近的機率 $ N $ 最多有它的所有素數 $ B_1 $ ; $ \displaystyle\sum_{B_1<q\le B_2\\quad q\in\Bbb P}\hat\rho\biggl(\frac{\log(N/q)}{\log(B_1)},N/q\biggr)/q $ 估計隨機整數附近的機率 $ N $ 有它的所有質因數，除了最大的至多 $ B_1 $ 並具有最大的因素 $ (B_1,B_2] $ ; 和 $ \delta $ 是對隨機素數這一事實的修正 $ p $ 靠近 $ N $ 有 $ p-1 $ 能被小素數整除 $ q $ 有機率 $ 1/(q-1) $ ， 而不是 $ 1/q $ 對於附近的隨機整數 $ N $ .
注意：該答案仍然缺少如何計算大的總和 $ B_2 $ . GMP-ECM 在以下情況下使用一些間接方法 $ q>20000 $ ，它總是用於在分解 RSA 模數時實際感興趣的參數。出於這個原因，我將問題設為社區 Wiki。
舉例說明：
ecm -pm1 35e9使用 $ B_1=35000000000 $ , $ B_2=81866328103009612 $ ，並找到一個 256 位隨機素數 $ P\approx0.0000119 $ . 在隨機 256 位素因子的 3 因子 RSA 768 位模積中找到一個因子，大約為 28000 模中的一個。使用一個核心和 48GiB RAM 測試一個模數大約需要 3.5 小時。大多數 RAM 的使用時間不到 25%，因此一台 4 核 CPU 64GiB 機器可以以每小時超過一個模數的速率進行測試。如果對手滿足於將任何一個因子分解為 3 萬個這樣的 RSA 模數，那麼 Polard 的 p-1 是一種合理的策略來提取一個因子（預期成本為 1170 CPU×天），然後是 GNFS 來分解一個 512 位的組合. 這僅勝過 GNFS，我相信 ECM。在這種設置中，以擊敗 Polard 的 p-1 和可能的 Williams 的 p+1 的方式生成素數是有意義的。感謝 Paul Zimmermann 和 Alexander Kruppa 的指導。
造成這種差異的原因是什麼？
主要問題：問題的術語 $ \displaystyle\frac{\log_2(B_2)}{\log_2(B_1)} $ 太高了。它應該是一個大隨機整數的第二高因子小於的機率的下限 $ B_1 $ ，知道最高因子小於 $ B_2 $ . 那是毫無根據和錯誤的。