您如何使費馬素性檢驗快速進行？
這個小 Lisp 函式以非常簡單的方式實現了費馬的素性檢驗，而且速度很慢 $ n >= 10^6 $ 因為我們進入了 bignum 領域。
(defun prime-p (n) (= 1 (mod (expt 5 (1- n)) n)))我錯過了什麼？我假設這不是 RSA 實現中實際使用的形式來找到合適的素數，實際使用的是什麼？
我不是很擅長閱讀 Lisp，所以如果我錯了，請糾正我，但看起來你好像在天真地計算 $ a^{n-1} \bmod n $ 通過首先提高 $ a $ 到 $ n-1 $ -th 次方，然後對結果取模 $ n $ .
這是實現模冪的一種非常低效的方法，因為正如您所注意到的，中間結果 $ a^{n-1} $ 可以迅速增長到巨大的規模。減少任何中間結果的模數要有效得多 $ n $ 在提升的同時 $ a $ 到 $ n-1 $ -th 次方，有效地直接在環中進行計算 $ \mathbb Z / n \mathbb Z $ 餘數模 $ n $ .
不幸的是，我對 Lisp 了解的不夠多，無法直接為您建議模冪運算的有效實現，但我上面連結的 Wikipedia 頁面確實描述了一些合適的算法，並提供了一些您可能能夠適應的迭代虛擬碼實現。
您不需要明確計算 $ a^{m-1} $ . 請注意 $ a^{2k} =(a^k)^2 $ 然後 $ a^{2k+1} = a \cdot (a^k)^2 $ .
這表明了一個簡單的遞歸函式 $ \phi(k) $ 確定 $ a^k $ 模組 $ m $ . 一、減少 $ a $ 模組 $ m $ . 那麼，如果 $ k $ 是奇數，返回 $ a \cdot \phi \left (\frac{k-1}{2} \right) \cdot \phi \left (\frac{k-1}{2} \right) $ 減少模 $ m $ ; 如果 $ k $ 甚至返回 $ \phi \left( \frac{k}{2} \right ) \cdot \phi \left( \frac{k}{2} \right ) $ 減少模 $ m $ .