最近看到一則頗為有趣的新聞，說北大一名大一新生，以素數(shù)為標準選手機號，受到廣大網(wǎng)友膜拜。其實素數(shù)的檢測算法是很有趣的，并且會涉及到數(shù)論、概率算法等諸多內(nèi)容，一直覺得素數(shù)探測算法是了解概率算法很好的入口。本文和大家簡單聊聊如何確定一個數(shù)是素數(shù)。

素數(shù)

素數(shù)的定義

素數(shù)是這樣被定義的：

一個大于1的整數(shù)，如果不能被除1和它本身外的其它正整數(shù)整除，則是素數(shù)（又稱質(zhì)數(shù)）。

與素數(shù)相關(guān)的定義還有合數(shù)：

一個大于1的整數(shù)，如果不是素數(shù)則是合數(shù)。其中能整除這個數(shù)的正整數(shù)叫做約數(shù)，不等于1也不等于合數(shù)本身的約數(shù)叫做非平凡約數(shù)。

注意1既不是素數(shù)又不是合數(shù)。

舉幾個例子：

2是素數(shù)，因為除1和2外沒有其它正整數(shù)可以整除2。

3也是素數(shù)。

4不是素數(shù)，因為2可以整除4。

11是素數(shù)，除1和11外沒有正整數(shù)可以整除它。

15不是素數(shù)，3和5可以整除15。

素數(shù)的性質(zhì)

素數(shù)有一些有趣的性質(zhì)，下面不加證明的列幾條。

素數(shù)有無窮多個。

設(shè)f(n)為定義在大于1的整數(shù)集合上的函數(shù)，令f(n)的值為不大于n的素數(shù)的個數(shù)，則：

limn→∞f(n)n/lnn=1limn→∞f(n)n/ln?n=1

這個函數(shù)叫做素數(shù)分布函數(shù)，反映了素數(shù)的分布律。換言之，可以認為大于1的前n個正整數(shù)中，素數(shù)的個數(shù)大約是n/lnnn/ln?n。

檢測素數(shù)

所謂素數(shù)檢測，就是給定任意一個大于1的整數(shù)，判斷這個數(shù)是否素數(shù)。

因子檢測法

最直觀的素數(shù)檢測算法就是因子檢測法。說白了，就是從2到n-1一個個拿來試，看能否整除n，如果有能整除的（找到一個因子），則輸出不是質(zhì)數(shù)，否則則認為n為質(zhì)數(shù)。當然，實際上不需要試探到n-1，只要到n√n就好了，原因如下：

設(shè)n=a×bn=a×b，且a、b均為n的非平凡約數(shù)，顯然a>n√a>n和b>n√b>n不可能同時成立，因為同時成立時a*b就會大于n，所以，如果n存在非平凡約數(shù)，則至少有一個小于等于n√n，因此只要遍歷到n√n就可以了。

因子檢測法的實現(xiàn)代碼如下（python）：

def prime_test_factor(n):

if n == 1:

return False

for i in range(2, 1 + int(floor(sqrt(n)))):

if n % i == 0:

return False

return True

做幾個測試：

print prime_test_factor(2) #True

print prime_test_factor(11) #True

print prime_test_factor(15) #False

print prime_test_factor(2147483647) #True

很明顯，因子檢測法的時間復雜度為O(n√)O(n)，一般來看，這個時間復雜度已經(jīng)很不錯了，不過對于超級大的數(shù)（例如RSA加密中找?guī)装傥坏乃財?shù)是很正常的），這個復雜度還是太大了。

例如對于下面的整數(shù)：

6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554 977296311391480858037121987999716643812574028291115057151

哪位壯士可以試試用因子檢測法檢測這個數(shù)是質(zhì)數(shù)還是合數(shù)，估計這輩子結(jié)果是出不來了，下輩子也懸。所以需要更高效的素數(shù)檢測算法。

費馬檢測

坦白說，對于大素數(shù)的探測，目前并沒有非常有效的確定性算法。不過借助費馬定理，可以構(gòu)造一種有效的概率算法來進行素數(shù)探測。

費馬定理

首先看一下什么是費馬定理。這條定理是史上最杰出的業(yè)余數(shù)學家費馬發(fā)現(xiàn)的一條數(shù)論中的重要定理， 這條定理可以表述為：

如果p為素數(shù)，則對任何小于p的正整數(shù)a有

ap?1≡1(mod?p)ap?1≡1(mod?p)

根據(jù)基本數(shù)理邏輯，一個命題正確，當且僅當其逆否命題正確。所以費馬定理蘊含了這樣一個事實：如果某個小于p的正整數(shù)不符合上述公式，則p一定不是素數(shù)；令人驚訝的是，費馬定理的逆命題也“幾乎正確”，也就是說如果所有小于p的正整數(shù)都符合上述公式，則p“幾乎就是一個素數(shù)”。當然，“幾乎正確”就意味著有出錯的可能，這個話題我們后續(xù)再來討論。至少從目前來看，費馬定理給我們提供了一條檢測素數(shù)的方法。

下面再通過例子說明一下費馬定理表達的意義，例如我們知道7是一個素數(shù)，則：

162636465666=1=64=729=4096=15625=46656≡1(mod?7)≡1(mod?7)≡1(mod?7)≡1(mod?7)≡1(mod?7)≡1(mod?7)16=1≡1(mod?7)26=64≡1(mod?7)36=729≡1(mod?7)46=4096≡1(mod?7)56=15625≡1(mod?7)66=46656≡1(mod?7)

其它素數(shù)可以可以用類似方法驗證，關(guān)于這個定理的嚴格證明本文不再給出。

所以可以使用如下方法進行大素數(shù)探測：選擇一個底數(shù)（例如2），對于大整數(shù)p，如果2^(p-1)與1不是模p同余數(shù)，則p一定不是素數(shù)；否則，則p很可能是一個素數(shù)。

至于出現(xiàn)假陽性（即合數(shù)被判定為素數(shù)）的概率，已有研究表明，隨著整數(shù)趨向于無窮，這個概率趨向于零，在以2為底的情況下，512位整數(shù)碰到假陽性的概率為1/10^20，而在1024位整數(shù)中，碰到假陽性的概率為1/10^41。因此如果使用此法檢測充分大的數(shù)，碰到錯誤的可能性微乎其微。

模冪的快速算法

僅有費馬定理還不能寫檢測算法，因為對于大整數(shù)p來說，a^(p - 1) (mod p)不是一個容易計算的數(shù)字，例如上上面那個超大整數(shù)來說，直接計算2的那么多次冪真是要死人了，其效果一點不比因子分解法好。所以尋找一種更有效的取模冪算法。通常來說，重復平方法是一個不錯的選擇。下面通過例子介紹一下這個方法。

假設(shè)現(xiàn)在要求2的10次方，一種方法當然是將10個2連乘，不過還有這樣一種計算方法：

10的二進制表示是1010，因此：

210=2[1010]2210=2[1010]2

現(xiàn)初始化結(jié)果d=2^0=1，我們希望通過乘上某些數(shù)變換到2^10，變換序列如下：

2[0]22[0]22[1]22[10]22[101]2×2[0]2×2[1]2×2[10]2×2[101]2×2×2=2[1]2=2[10]2=2[101]2=2[1010]22[0]22[0]2×2[0]2×2=2[1]22[1]2×2[1]2=2[10]22[10]2×2[10]2×2=2[101]22[101]2×2[101]2=2[1010]2

可以看到這樣一個規(guī)律：對中間結(jié)果d自身進行平方，等于在二進制指數(shù)的尾部“生出”一個0；對中間結(jié)果d自身進行平方再乘以底數(shù)，等于在二進制指數(shù)尾部“生出”一個1?？窟@樣不斷讓指數(shù)“生長”，就可以構(gòu)造出冪。如果在每次運算時取模，就可以得到模冪了，下面是這個算法的python實現(xiàn)：

def compute_power(a, p, m):

result = 1

p_bin = bin(p)[2:]

length = len(p_bin)

for i in range(0, length):

result = result**2 % m

if p_bin[i] == '1':

result = result * a % m

?

return result

這個算法的復雜度正比于a、p和m中位數(shù)最多的數(shù)的二進制位數(shù)，要遠遠低于樸素的模冪求解法。

例如，下面的代碼在我的機器上瞬間可以完成：

compute_power(2, 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057150, 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151)

而用直觀方法計算如此大指數(shù)的冪基本是不可能的。

費馬檢測的實現(xiàn)

有了上的鋪墊，下面可以實現(xiàn)費馬檢測了：

def prime_test_fermat(p):

if p == 1:

return False

if p == 2:

return True

d = compute_power(2, p - 1, p)

if d == 1:

return True

return False

以下是一些測試：

print prime_test_fermat(7) #True

print prime_test_fermat(11) #True

print prime_test_fermat(15) #False

print prime_test_fermat(121) #False

print prime_test_fermat(561) #True

print prime_test_fermat(6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151) #True

需要注意的是，倒數(shù)第二個結(jié)果實際是錯的，因為561可以分解為3和187。

相對來說，因子分解法適合比較小的數(shù)的探測，可以給出準確的結(jié)論，但是對于大整數(shù)效率不可接受，例如上面最后一個超大整數(shù)，因子分解法基本不可行；費馬測試當給出否定結(jié)論時，是準確的，但是肯定結(jié)論有可能是錯誤的，對于大整數(shù)的效率很高，并且誤判率隨著整數(shù)的增大而降低。

Miller-Rabin檢測

上文說，費馬檢測失誤的概率隨著整數(shù)不斷增大而趨向于0，看似是對大素數(shù)檢測很好的算法。那么我們考慮另外一個問題：如果一個數(shù)p是合數(shù)，a是小于p的正整數(shù)且a不滿足費馬定理公式，那么a叫做p是合數(shù)的一個證據(jù)，問題是，對于任意一個合數(shù)p，是否總存在證據(jù)？

答案是否定的。例如561這個數(shù)，可以分解為3乘以187，但是如果你試過會發(fā)現(xiàn)所有小于561的正整數(shù)均符合費馬定理公式。這就意味著，費馬檢測對于561是完全失效的。類似561這樣是合數(shù)但是可以完全欺騙費馬檢測的數(shù)叫做Carmichael數(shù)。Carmichael數(shù)雖然密度不大（前10億個正整數(shù)中約600個），但是已經(jīng)被證明有無窮多個。Carmichael數(shù)的存在迫使需要一種更強的檢測條件配合單純費馬檢測使用，其中Miller-Rabin檢測是目前應用比較廣泛的一種。

Miller-Rabin檢測依賴以下定理：

如果p是素數(shù)，x是小于p的正整數(shù)，且x^2 = 1 mod p，則x要么為1，要么為p-1。

簡單證明：如果x^2 = 1 mod p，則p整除x^2 - 1，即整除(x+1)(x-1)，由于p是素數(shù)，所以p要么整除x+1，要么整除x-1，前者則x為p-1，后者則x為1。

以上定理說明，如果對于任意一個小于p的正整數(shù)x，發(fā)現(xiàn)1（模p）的非平凡平方根存在，則說明p是合數(shù)。

對于p-1，我們總可以將其表示為u2^t，其中u是奇數(shù)，t是正整數(shù)。此時：

ap?1=au2t=(au)2tap?1=au2t=(au)2t

也就是可以通過先算出a^u，然后經(jīng)過連續(xù)t次平方計算出a^(p-1)，并且，在任意一次平方時發(fā)現(xiàn)了非平凡平方根，則斷定p是合數(shù)。

例如，560 = 35 * 2^4，所以可設(shè)u=35，t=4：

23526321662672mod561=263mod561=166mod561=67mod561=1235mod561=2632632mod561=1661662mod561=67672mod561=1

由于找到了一個非平凡平方根67，所以可以斷言561是合數(shù)。因此2就成為了561是合數(shù)的一個證據(jù)。

一般的，Miller-Rabin算法的python實現(xiàn)如下：

def miller_rabin_witness(a, p):

if p == 1:

return False

if p == 2:

return True

?

n = p - 1

t = int(floor(log(n, 2)))

u = 1

while t > 0:

u = n / 2**t

if n % 2**t == 0 and u % 2 == 1:

break

t = t - 1

?

b1 = b2 = compute_power(a, u, p)

for i in range(1, t + 1):

b2 = b1**2 % p

if b2 == 1 and b1 != 1 and b1 != (p - 1):

return False

b1 = b2

if b1 != 1:

return False

?

return True

?

def prime_test_miller_rabin(p, k):

while k > 0:

a = randint(1, p - 1)

if not miller_rabin_witness(a, p):

return False

k = k - 1

return True

其中miller_rabin_witness用于確認a是否為p為合數(shù)的證據(jù)，prime_test_miller_rabin共探測k次，每次隨機產(chǎn)生一個1至p-1間的整數(shù)。只要有一次發(fā)現(xiàn)p為合數(shù)的證據(jù)就認為p為合數(shù)，否則認為p為素數(shù)。一些測試：

print prime_test_miller_rabin(7, 5) #True

print prime_test_miller_rabin(21, 5) #False

print prime_test_miller_rabin(561, 50) #False

print prime_test_miller_rabin(6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151, 50) #True

Miller-Rabin檢測也同樣存在假陽性的問題，但是與費馬檢測不同，MR檢測的正確概率不依賴被檢測數(shù)p（排除了Carmichael數(shù)失效問題），而僅依賴于檢測次數(shù)。已經(jīng)證明，如果一個數(shù)p為合數(shù)，那么Miller-Rabin檢測的證據(jù)數(shù)量不少于比其小的正整數(shù)的3/4，換言之，k次檢測后得到錯誤結(jié)果的概率為(1/4)^k，例如上面最后一個大整數(shù)，Miller-Rabin檢測認為其實素數(shù)，我設(shè)k為50，也就是說它被誤認為素數(shù)的概率為(1/4)^50。這個概率有多小呢，小到你不可想象。直觀來說，大約等于一個人連續(xù)中得5次雙色球頭獎的概率。

參考文獻

[1]?算法導論

[2]?http://www.wikipedia.org/

[3]?http://www.matrix67.com/blog/archives/234

[4]?http://www.bigprimes.net/

from:?http://blog.codinglabs.org/articles/prime-test.html

總結(jié)

以上是生活随笔為你收集整理的聊聊如何检测素数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。