在資訊安全領域，經常需要用到一些大素數，比如著名的RSA算法就必須依賴到兩個大素數。幸運的是自然數中素數還真不少(很簡單就能證明素數有無窮多個)，而且密度也不算低，是以找到一個素數不是那麼難，但讓你找一個能用在RSA算法裡的素數就比較難了。
暴力試除
試想下，如果現在讓你去尋找出一個素數，你會怎麼辦？記得剛上大學剛學會C語言基本文法後，有道課後題就是判定一個數是否是素數，具備基本程式設計能力的人一定能寫出如下代碼：
boolean checkPrime(int n) {
for (int i = 2; i*i <= n; i++) {
if (n%i == 0) {
return false;
}
}
return true;
} 素數判定最簡單的方法就是試除，也就是上面代碼。它的原理是從2到根号n，看n是否能被某個數除盡，如果能那n肯定不是素數，反之一定是素數。這确實是個簡單粗暴且正确的方法，唯一的問題是它太慢了，判定一個數的時間複雜度是O(n)。如果讓你用這種方法去判斷一個幾百位的數是否是素數，那可能用現在最先進的計算機，也需要n多年才能算出來。
篩選法
當然素數判定還有一個更快的批量判定算法——埃氏篩選，他找到n以内的所有素數隻需要
O(n log log n)
的時間複雜度。
其原理是這樣的，設定一個标記數組，開始先把2的所有倍數都标記了，然後往後走發現3沒有被标記，那3肯定是個素數，然後在标記數組中把所有3的倍數标記掉，然後發現4已經被标記了 跳過，到5……，直到标記完所有數字，那麼剩下未标記的數字就是素數了，見上圖，代碼如下：
int[] signs = new int[n+1];
void eratosthenes(int n) {
for (int i = 2; i <= n; i++) {
if (signs[i] == 0) {
for (int j = i * i; j <= n; j += i) {
signs[j] = 1;
}
}
}
} 埃氏篩選法雖然看起來比較快，但他也有自己的問題。首先他隻能批量，對單個的n判定時也是需要篩出所有小于n的素數的。其次，它還需要依賴存儲空間來存儲标記。是以它仍然無法被用在超大素數的判定上。
有沒有更快找到一個素數的方法？自從中世紀以來，有好多的數學家都在緻力于尋找傳中的素數公式。比如歐拉在1772年發現，
費馬小定理
然而，事情總是有轉機的。讓我們一起回到1636年，著名數學家費馬在一封信中寫出這樣一個公式。
如果p是一個素數，且a不是p的倍數，則有a^(p-1) ≡ 1(mod p)
後來證明a不是p的倍數這個條件不是必須的。 這個定理的含義就是隻要p是素數，那麼恒等于1，這就是著名的費馬小定理。可能你已經在想，能不能用這個定理來判定素數，确實費馬小定理反過來也幾乎是成立的，如果一個數p能使得a^(p-1) ≡ 1(mod p)，p有很大機率是個素數，注意這裡是幾乎成立。
public class PrimeNumCheck {
public static boolean check(long a, long p) {
long res = fastMod(a, p-1, p);
return res == 1;
}
public static long fastMod(long x, long n, long m) {
if (n == 1) {
return x % m;
}
long tmp = fastMod(x, n>>1, m);
if (n % 2 == 0) {
return (tmp * tmp) % m;
} else {
return (tmp * tmp * x) % m;
}
}
public static void main(String[] args) {
System.out.println(check(2, 7));
}
} 用如上Java代碼，可以快速的機率性判定一個數是否是素數（判定結果不是100%準确），這也取決于上述代碼中a的選擇。上面用到了快速幂算法，能将對一個數的n次幂取模的時間複雜度降到O(logn)。我們似乎可以将素數的判定時間複雜度從O(n)降低到O(logn)，這是質的飛躍，從原來的幾乎不可計算變為可計算，這才為大素數的應用鋪平了道路。
但是别急，它還有些小缺陷。我剛說了費馬小定理反過來是幾乎成立的，我一直在強調幾乎二字。因為有些和數n也能使得成立，這些使得的合數被稱為基于a僞素數，比如前幾個基于2的僞素數分别是341、561、645……。不過這種僞素數也非常少，實際上，**對于一個512位的數，其中基于2的僞素數不到1/1020**，如果是1024位的數的話，僞素數機率就隻有不到1/1041了。這個機率究竟有多低，舉個例子，你能随機找到一個512位基于2的僞素數的機率比你中五百萬大獎的機率都小。 是以你是随機找一個素數，基于2的費馬小定理判定已經足夠用了。
當然如果你非要追求更高準确率的話，還是可以優化的，畢竟基于2的僞素數并不一定是基于其他a的僞素數，是以我們可以多換幾個不同的a來進一步提升上述代碼的準确性。 但曆史告訴我們凡事總有意外。有些合數對于任意的a都能使得費馬定理成立，這些數被稱為卡邁克爾數(Carmichael Number)，前幾個卡邁克爾數分别是561 1105 1729…… 關于卡邁克爾數又是另一個故事了。
小結
參考資料
- 維基百科 素數測試
- 維基百科 埃氏篩選 Sieve of Eratosthenes
- 維基百科 卡邁克爾數
- 《算法導論》 第31章 素數測試