我們必須測試的奇數個數，直到找到一個任意 RSA 模數大小的素數
流行的 RSA 模數大小是 $ 1024 $ , $ 2048 $ , $ 3072 $ 和 $ 4092 $ 少量。在我們期望找到一個素數之前，我們平均需要測試多少個隨機奇數？我大致知道每一個 $ \ln p $ 整數有素數。為一個 $ 1024 $ 少量 $ p $ , $ \ln p = 710 $ . 平均而言，需要測試大約 $ 710/2=355 $ 在找到素數之前的奇數。是真的嗎，我們可以提取公式嗎 $ (\ln p)/2 $ 對於任何任意 RSA 模數大小？
對於 n 位 RSA，您需要找到乘積為 n 位數字的兩個素數，每個素數約為 n/2 位。實際上一個小一點，一個大一點，因為你不希望素數靠得太近。
M 周圍的 ln M 個數中大約有一個是素數；這是自然對數。ln (2) 接近 0.7。如果 M = 2^(n/2)，則 ln M ≈ 0.35n。您只檢查奇數，它們是素數的可能性是素數的兩倍，機率為 2 / 0.35n。測試 0.175n 個奇數會找到一個素數。你需要兩個，所以大約 0.35n。
但請注意，其中許多除數很小，可以很快辨識出來；例如，通過使用篩子去除因子 < 1000 或 10,000 的數字。要接受素數，您將執行 Miller-Rabin 測試 50 或 100 次，而對於 3/4 的非素數，您執行一次，對於其餘的 3/4，您執行兩次等等。關鍵是測試非素數的素數通常很快。測試兩個實際素數需要很長時間。您測試素數的複合材料的數量並不重要。
PS我剛剛意識到每個人都高估了2倍。假設我決定想要一個接近奇數K的素數，所以我測試K、K+2、K+4等，直到遇到素數。設p是小於K的最大素數，q是第一個素數>=K。要測試的off數不是gap，除以2（因為我們只測試奇數）而是一半，因為K可以在那個間隙的任何地方。
PPS 我剛剛意識到那個論點有問題……
不，你錯了，因為
我知道大致每個 ln p 整數都有一個素數。
是一個粗略的估計，實際上是錯誤的。
素數計數函式的估計 $ \Pi(p)=p /ln(p) $ 估計 0 到 0 之間的總素數 $ p $ . 因此，對於具有 x 位的數字，您需要查看 $ \Pi(2^{x}) - \Pi(2^{x-1}) $ 並將其與候選人總數進行比較，即 $ 2^{x-2} $ ，當你只考慮奇數時。
你離得不遠，對於大數來說差異很小，但公式並不是那麼簡單。