為什麼 PGP 仍然使用費馬素性檢驗？如果它達到卡邁克爾數之一怎麼辦？
由於費馬素性檢驗不是很可靠，大多數應用程序僅將其用於預測試。維基百科說 PGP 仍然使用它：
另一個僅依賴於 Fermat 測試的知名程序是 PGP，它僅用於測試自生成的大隨機值（開源對應物 GNU Privacy Guard，使用 Fermat 預測試，然後是 Miller-Rabin 測試）。
我不明白為什麼 PGP 仍然使用它而不遵循 Miller-Rabin 測試。如果它達到卡邁克爾數字怎麼辦？
堅持費馬測試是PGP設計者的選擇。自 1994 年以來有一些很好的談話
最後的報價；
卡邁克爾數字
不幸的是，有些數字不是素數，但確實滿足等式 $ b^{n-1} \bmod n $ . 這些整數被稱為卡邁克爾數，它們非常罕見。原因是卡邁克爾數不能被任何素數的平方整除，並且必須是至少三個素數的乘積）。卡邁克爾數的前三個分別是：561、1105、1729。它們是如此的稀有，實際上只有不到255個 $ 10^9 $ . PGP 產生卡邁克爾數的機會小於 1 in $ 10^{50} $ .
因此，即使有其他替代費馬測試的方法，他們仍然使用它。
這裡是卡邁克爾數的oeis/A002997 ；
- 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461
如果它達到卡邁克爾數，那麼它將分解為較小的素數，例如 $ 512461 =31 \cdot 61 \cdot 271 $ . 但它仍然可以像普通的 RSA 一樣工作並愚弄我們。
一旦獲得快速可能的素數，就可以使用證明方法而不是 AKS。我們可以將其視為現代篩分。
- 1993，Atkin 和 Morain，Elliptic Curve 和 Primality Proving，它還可以提供用於快速驗證的素性證書，這在AKS中是不可能的，其中數字本身被視為其素數的自我證明。
- 1983,1984，Adleman-Pomerance-Rumely 素性檢驗
如果要使用 AKS，請使用更快的 AKS 變體測試。請注意，AKS 是一種緩慢且確定性的素數證明算法。這裡引用 DanaJ 在 Math.SE 中的最佳答案查找給定數字是否為素數的最快方法
任何建議在實踐中實際使用 AKS 的人從未真正在大於 10,000 的數字上執行過它，因此應該被忽略。