天天看點

素數判定 進階程式員才知道的那些事兒

在資訊安全領域,經常需要用到一些大素數,比如著名的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章 素數測試

繼續閱讀