有沒有容易在 40 位到 60 位內取模的素數？

我想實現基於 LWE 的加密方案，模 $ q $ 可以分解為 $ q = q_0\cdot q_1\cdots q_k $ 根據 CRT。我猜模運算由 $ q_i $ 是關鍵操作，所以我盡量選擇梅森素數。但是，只有兩個素數滿足： $ 2^{31}-1 $ 和 $ 2^{61}-1 $ .

是否還有其他素數，例如 $ 2^n-b $ 很容易取模（最好介於 $ 2^{40} $ 和 $ 2^{60} $ )?

首先，這顯然是正確的，沒有限制 $ b $ . 例如，對於 $ b = 2^n-2 $ 我們明白了 $ 2^n - b = 2^n - (2^n-2) = 2 $ 是素數。這很無聊，可能不是你的意思（相反，我想你想要 $ b $ 小）。

有多小 $ b $ 我們應該期望這種情況持續嗎？素數定理的一種解釋是素數具有“密度 $ 1/\ln x $ ”。這就是說，當 $ x = 2^{40} $ 至 $ 2^{60} $ ，我們（大致）期望 $ \approx 1/40 $ 至 $ 1/60 $ 數為素數。有多種方法可以將其形式化（取決於您是否相信黎曼假設），請參閱此頁面，尤其是“概括”部分。

無論如何，外賣應該是

1. 素數相對“豐富”，所以
2. 找到（你想要的形式的）素數，“看看”。

這就是說，編寫一個搜尋最小正數的程序很簡單 $ b $ 這樣 $ 2^n-b $ 是素數。下面是一個 Sage 程序，應該展示事情是多麼簡單（前提是實現了素性測試）。

def find_b(n):
   q = 2**n
   b = 0
   while not (q-b).is_prime():
       b += 1
   return b

由於您對以下情況感興趣 $ 2^{40} $ 至 $ 2^{60} $ ，我在下面為你計算了這些

$$ (40, 87), (41, 21), (42, 11), (43, 57), (44, 17), (45, 55), (46, 21), (47, 115), (48, 59), (49, 81), (50, 27), (51, 129), (52, 47), (53, 111), (54, 33), (55, 55), (56, 5), (57, 13), (58, 27), (59, 55), (60, 93) $$. 數據格式是這樣的 $ (a,b) $ 表示數字 $ 2^a-b $ ，所以例如第一個條目是數字 $ 2^{40}-87 $ . 上面列表中的所有數字都是素數。此外，選擇 $ b $ 在上面是（如前所述）總是最小的選擇，使得 $ (a,b) $ 是素數。執行這個程序非常高效，在我的桌面上用了不到一秒鐘。

---

話雖如此，精確的結構 $ q_i $ 承認有效算術比您描述的要復雜一些，至少在執行 Ring-LWE 類型的事情時（您使用多項式算術）。在這裡，能夠利用數論變換（即使只是“不完整”的變換）非常有用。這對所選模數的精確形式提出了相當嚴格的要求（對於完整的 NTT，您需要 $ q\equiv 1\bmod 2n $ 工作時 $ \mathbb{Z}_q[x]/(x^n+1) $ iirc)。話雖如此，這些優化可能在技術上涉及更多，因此在學習加密時可能應該首先跳過。

我想實現基於 LWE 的加密方案，模 $ q $ 可以分解為 $ q = q_0\cdot q_1\cdots q_k $ 根據 CRT。

實際上，要使 CRT 起作用，所必需的只是這些因數是互質的，它們不需要單獨質數。 $ 2^x-1 $ 和 $ 2^y-1 $ 每當 $ x $ 和 $ y $ 是; 因此，您所需要的只是該範圍內的一組指數 $ [40, 60] $ 是相對優質的。

一個明顯的選擇是使用因子 $ 2^{p}-1 $ 為了 $ p \in {41, 43, 47, 49, 53, 55, 57, 58, 59} $ （我相信，這是該範圍內具有最大總和的互質值集）；這可能足以滿足您的需求（如果 $ q \approx 2^{462} $ 足夠大）

引用自：https://crypto.stackexchange.com/questions/99926