本文實例講述了Python素數檢測的方法。分享給大家供大家參考。具體如下：

因子檢測：

檢測因子，時間復雜度O(n^(1/2))

def is_prime(n):

if n < 2:

return False

for i in xrange(2, int(n**0.5+1)):

if n%i == 0:

return False

return True

費馬小定理：

如果n是一個素數，a是小于n的任意正整數，那么a的n次方與a模n同余

實現方法：

選擇一個底數（例如2），對于大整數p，如果2^(p-1)與1不是模p同余數，則p一定不是素數；否則，則p很可能是一個素數

2**(n-1)%n 不是一個容易計算的數字

模運算規則：

(a^b) % p = ((a % p)^b) % p

(a * b) % p = (a % p * b % p) % p

計算X^N(% P)

可以

如果N是偶數，那么X^N =（X*X）^[N/2]；

如果N是奇數，那么X^N = X*X^(N-1) = X *（X*X）^[N/2]；

def xn_mod_p(x, n, p):

if n == 0:

return 1

res = xn_mod_p((x*x)%p, n>>1, p)

if n&1 != 0:

res = (res*x)%p

return res

也可以歸納為下面的算法 兩個函數是一樣的

def xn_mod_p2(x, n, p):

res = 1

n_bin = bin(n)[2:]

for i in range(0, len(n_bin)):

res = res**2 % p

if n_bin[i] == '1':

res = res * x % p

return res

有了模冪運算快速處理就可以實現費馬檢測

費馬測試當給出否定結論時，是準確的，但是肯定結論有可能是錯誤的，對于大整數的效率很高，并且誤判率隨著整數的增大而降低

def fermat_test_prime(n):

if n == 1:

return False

if n == 2:

return True

res = xn_mod_p(2, n-1, n)

return res == 1

MILLER-RABIN檢測

Miller-Rabin檢測是目前應用比較廣泛的一種

二次探測定理:如果p是一個素數,且0<x<p,則方程x^2%p=1的解為:x=1或x=p-1

費馬小定理：a^(p-1) ≡ 1(mod p)

這就是Miller-Rabin素性測試的方法。不斷地提取指數n-1中的因子2，把n-1表示成d*2^r（其中d是一個奇數）。那么我們需要計算的東西就變成了a的d*2^r次方除以n的余數。于是，a^(d * 2^(r-1))要么等于1，要么等于n-1。如果a^(d * 2^(r-1))等于1，定理繼續適用于a^(d * 2^(r-2))，這樣不斷開方開下去，直到對于某個i滿足a^(d * 2^i) mod n = n-1或者最后指數中的2用完了得到的a^d mod n=1或n-1。這樣，Fermat小定理加強為如下形式：

盡可能提取因子2，把n-1表示成d*2^r，如果n是一個素數，那么或者a^d mod n=1，或者存在某個i使得a^(d*2^i) mod n=n-1 ( 0<=i<r ) （注意i可以等于0，這就把a^d mod n=n-1的情況統一到后面去了）

定理:若n是素數,a是小于n的正整數,則n對以a為基的Miller測試,結果為真.

Miller測試進行k次,將合數當成素數處理的錯誤概率最多不會超過4^(-k)

def miller_rabin_witness(a, p):

if p == 1:

return False

if p == 2:

return True

#p-1 = u*2^t 求解 u, t

n = p - 1

t = int(math.floor(math.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 = xn_mod_p2(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

希望本文所述對大家的Python程序設計有所幫助。