除了1和自己以外，沒有任何因子的數都稱為素數，也叫質數。

素數的產生藉助計算機用C語言或者VB，運算有電腦完成，應該是很快的。但若是單憑口算和筆算，那怕是要廢了！

我們都知道100以內的素數：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47……

但是要上百上千口算都應付不過來了，何況是1024位的大素數呢？所以，還是用程式吧！

然而，就這個問題，有一件搞笑的事是日本年初出版了一本書《2017年最大的素數》，這本書用了719頁只印了1個素數，這也是迄今為止發現的最大的素數。這個數是2^77,232,917-1，共計23249425位。

如果你對一個有兩千多萬位的數沒概念，看看這本書也許會明白它有多大。

所以，1024位的大素數應該不算事！！！

可能有點不可思議的是，產生大素數，或者說生成一個很大的而且幾乎確定是素數的數，這件事並不需要費多少時間。在現代的家用計算機上，只要幾秒鐘即可。

首先，根據素數定理，N附近的素數密度大概是1/ln(N)。也就是說，大概在N附近取ln(N)個數，就有一個是素數。因為對數函式增長得很慢，所以其實需要取的數並不是很多。對於1024二進位制位的素數來說，也就是一千不到。

然後就是測試素數的辦法。只要透過一些簡單的驗算，比如求對於420的模，就能篩選掉很大一部分的合數。剩下的就需要利用素性檢驗的演算法來驗證了。素性檢驗的演算法有不少，主要分為兩類：確定性演算法和機率性演算法。

確定性演算法的代表有Pocklington演算法和ECPP（橢圓曲線素性檢驗）演算法。兩者給出的實際上是某個數的確是素數的證明。在這裡簡單介紹一下Pocklington演算法，ECPP的原理是類似的。

Pocklington演算法依靠的是Pocklington定理：對於正整數N，如果有一個素數q，它大於N的平方根，又可以整除N-1，又存在另一個整數a，使得a^(N-1)模N等於1，而a^((N-1)/q)-1與N互質的話，那麼N就必定是素數。要利用這個定理，就要找到對應的q和a。如果知道q的話，找a並不是太難，只要隨機選取，成立的機率都不會太差。但是要找到q的話，就必須完全分解N-1這個數，但我們知道大數分解需要大量時間。所以，只有對一些特定的N，Pocklington演算法才能有效地證明N是素數。當然，這個演算法有一些別的版本，它們不需要q是素數這個條件，但仍然需要進行大數分解。ECPP也是類似的，不過用於驗證的是橢圓曲線。正因為這些演算法大多需要進行大數分解型別的步驟，一般人們很少使用它們來進行素性檢驗，只有在非常特殊，需要完全確定的時候才會用到。

機率性演算法的代表則是Miller-Rabin演算法。與其說它們是素性檢驗的演算法，不如說它們是驗證一個數不是素數的方法。如果重複多次，仍然找不到N不是素數的證據，我們就說N很有可能是素數。演算法本身很簡單。對於正奇數N，它可以寫成2^r*d+1，其中d是一個奇數。然後，隨機選取一個a，順次計算a^d，a^2d，……，a^(2^r*d)，檢驗是否滿足a^d模N餘1，而其他模N餘-1。如果不滿足的話，那麼N必定是合數；但如果滿足，也不能排除N是合數的可能性。Miller-Rabin在一次檢驗中出錯的機率是1/4，如果施行k次檢驗後仍然不能排除，我們就可以說N不是素數的機率是(1/4)^k。只要檢驗上千次，N不是素數的機率可以忽略不計。如果承認所謂的“廣義黎曼猜想”的話，甚至可以確定，只需要驗證2(ln(n))^2次，就能完全確定N是不是素數。目前這個方法還沒有出現反例。

在實用中，一般會使用Miller-Rabin演算法，只要重複足夠的次數，就能將出錯機率降低到硬體本身出錯的機率。總體來說，從隨機選擇到素性檢驗，整個過程運算的次數大概在十億量級，在家用計算機上也就是幾秒鐘的事情。