為什麼 GnuPG 在生成素數時會保存一組餘數？

在查看 GPG 的gen_prime()函式時，在 的cyphers/primegen.c文件中找到libgcrypt，我注意到這些函式保存了一個餘數列表，該列表將初始隨機生成的大數除以前 669 個左右的小素數。這樣做的目的是什麼？我在文件中看不到這樣做的任何理由。

他們正在做的是做一個快速測試，看看候選素數prime+step是否有任何最小的 669 個素數作為因子（通過測試是否prime%p + step是小素數的倍數p。如果他們確實發現候選素有一個小因子，那麼它顯然不是素數（因此他們不需要花費相對較長的時間來執行費馬測試）。

話雖這麼說，primegen.c 中的程式碼本可以更有效地完成。更常見的是創建一個篩子；也就是說，您創建一個初始清晰的點陣圖，對應於 ; 的前（可能）2000 個條目prime+step。對於每個小素數p，您計算prime%p並基於該值，標記點陣圖中對應於倍數的每個條目p. 完成此操作後，您可以單步執行位遮罩；任何仍然清晰的位對應於一個具有不小的因素的條目；然後，您可以對其進行昂貴的素性測試。這種方法的好處是每個小因素只需要處理一次；這意味著使用更多的小素數進行測試會更有效（因此您可以在素數搜尋的廉價部分消除更多的複合物）

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