整數分解的最壞情況
根據算術基本定理，每個大於 1 的整數要麼是素數本身，要麼是素數的乘積，並且這個乘積是唯一的，直到因子的順序。
$$ n=p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_r^{e_r} $$ 為了分解，最壞的情況是如果合數是兩個大素數的乘積。（一般性發言）
在RSA 密鑰生成中，說明如下
出於安全目的，整數 p 和 q 應該隨機選擇，並且應該在大小上相似但“長度相差幾個數字”以使分解變得更加困難。
在Paillier 密鑰生成中，說明如下
隨機且相互獨立地選擇兩個大素數 p 和 q，使得 $ \gcd(pq,(p-1)(q-1))=1 $ . **如果兩個素數長度相等，**則可以確保此性質。
我的疑問是，整數分解問題的實際最壞情況是什麼？
$ n=pq $ 和 $ length(p) = length(q) $ $ \ge $ k，對於一些 $ k \ge 1024,2048 \cdots $
$ n=pq $ 和 $ |length(p)-length(q)| \le k $ ， 對於一些 $ k \ge 1,2,3\cdots $
提供參考，說明整數分解的最壞情況，具體值為 $ k $
我的疑問是，整數分解問題的實際最壞情況是什麼？
…
提供參考，說明具有特定 k 值的整數分解的最壞情況
對於任何一類算法根本無法做到這樣的陳述，只有特定的算法才能具有最壞情況的執行時間。
一般來說，最壞情況估計幾乎沒有用於密碼學，因為平均情況更重要。下面是一個例子：假設你有一個新的假設分解算法，它對幾乎所有輸入上的合數都有線性執行時間，但對於階乘函式的值，它有指數執行時間。現在最壞情況下的執行時間是指數級的，但平均值只是線性的。更糟糕的是：在 $ x! $ 作為輸入，輸入除以 $ 2 $ 什麼時候 $ x>1 $ ，所以只需執行算法 $ x!/2 $ 相反，它的線性執行時間。這將使因式分解對密碼學完全無用 - 但該算法具有指數最壞情況執行時間。最壞情況假設只有在您可以以某種方式將平均情況減少到最壞情況（可能在隨機減少等情況下）時才有用 - 例如在基於格的密碼學中，這些方法適用。
在查看已知的因式分解算法時，有一些與最小素因子的大小成比例，一些與數字的總長度成比例，還有一些與“素因子的接近度”有關。為了對抗所有這些，通常會提出類似您發現的建議。然而，這些建議是參考已知算法而提出的，而這些算法並未以任何方式得到證明。
為了獲得實際的目前最先進的建議，keylength.com列出了各種來源的建議以及發布日期。最新的一個參考了 2017 年 2 月的 BSI 出版物：德文出版，編輯：找到英文版本
它在 RSA 小節中有以下建議：
$ \epsilon_1 < |\log_2(p) - \log_2(q)| < \epsilon_2 $
邊界的建議值為： $ \epsilon_1 \approx 0.1, \epsilon_2 \approx 30 $ . 價值 $ 0.1 $ 因為該指標意味著 $ p/q $ 不同於 $ 1 $ 至少一個因素 $ \approx 1.07177346 $ ，這大致意味著如果給定較小的素數 $ p $ ， 那 $ q > (1+\frac{1}{14})p $ ，這反過來意味著長度 $ b $ 素數，差值至少應為 $ b-4 $ 位（這意味著區別是 $ 1/16 $ , 但應該是 $ 1/14 $ 或者更多）。