生成 N 位素數 -> 實際範圍是多少？
簡短版本：當生成 N 位的素數時，我應該從該範圍內抽取隨機數嗎 $ [0 , 2^n] $ ， 或者 $ [2^{(n-1)} , 2^n] $ ?
背景：我正在嘗試實現一個玩具版本的 RSA 作為一種愛好，並使用 Miller-Rabin 測試來生成素數。最初，我生成密鑰的函式具有以下簽名：
$$ generateKeys :: (Range, Seed) \rightarrow (PublicKey, PrivateKey) $$ 其中 Range 是生成隨機數以搜尋素數的數字範圍，最初我設置為 $ [2^{16}, 2^n] $ 為了避免 $ [0-2^{16}] $ 範圍，因為 RSA 實施指南建議避免使用小素數。
但我開始想知道是否應該指定
$$ generateKeys :: (BitsToUse, Seed)\rightarrow (PublicKey, PrivateKey) $$ 這反過來又讓我想知道“N位素數”究竟是什麼意思，即通常需要從哪個範圍中選擇素數，特別是因為範圍 $ [2^{(n-1)}, 2^n] $ 是“僅”一半大小 $ [0 , 2^n] $ ，儘管我猜素數在該範圍內的密度要小一些。
在 RSA 的上下文中，當我們說“N 位素數”時，我們的意思是它是范圍內的素數 $ [2^{n-1}, 2^n) $ .
此外，當我們說 RSA 密鑰是“N 位密鑰”時，我們的意思是它在範圍內 $ [2^{n-1}, 2^n) $ . 這意味著如果你隨機選擇兩個 $ N/2 $ 位素數，並將它們相乘，你會得到一個 $ N-1 $ 位模數的一半左右。為了避免這種情況，一種常見的做法是從範圍中選擇素數 $ (\sqrt{2}\cdot 2^{n/2-1}, 2^{n/2}) $ - 這樣，當我們將兩個素數相乘時，我們總是會得到一個 N 位密鑰。
如果您擔心將素數限制在這個範圍內會使猜測它們變得更容易，那麼這實際上不是問題。如果我們生成一個 1024 位的密鑰（按照今天的標準，這已經接近了），大約有 $ 10^{151} $ 範圍內的素數 $ (\sqrt{2}\cdot 2^{511}, 2^{512}) $ - 任何人都不太可能猜到任何一個。