Python素數(shù)檢測的方法
本文實例講述了Python素數(shù)檢測的方法。分享給大家供大家參考。具體如下:
因子檢測:
檢測因子,時間復(fù)雜度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是一個素數(shù),a是小于n的任意正整數(shù),那么a的n次方與a模n同余
實現(xiàn)方法:
選擇一個底數(shù)(例如2),對于大整數(shù)p,如果2^(p-1)與1不是模p同余數(shù),則p一定不是素數(shù);否則,則p很可能是一個素數(shù)
2**(n-1)%n 不是一個容易計算的數(shù)字
模運(yùn)算規(guī)則:
(a^b) % p = ((a % p)^b) % p (a * b) % p = (a % p * b % p) % p
計算X^N(% P)
可以
如果N是偶數(shù),那么X^N =(X*X)^[N/2];
如果N是奇數(shù),那么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
也可以歸納為下面的算法 兩個函數(shù)是一樣的
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
有了模冪運(yùn)算快速處理就可以實現(xiàn)費馬檢測
費馬測試當(dāng)給出否定結(jié)論時,是準(zhǔn)確的,但是肯定結(jié)論有可能是錯誤的,對于大整數(shù)的效率很高,并且誤判率隨著整數(shù)的增大而降低
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檢測是目前應(yīng)用比較廣泛的一種
二次探測定理:如果p是一個素數(shù),且0<x<p,則方程x^2%p=1的解為:x=1或x=p-1
費馬小定理:a^(p-1) ≡ 1(mod p)
這就是Miller-Rabin素性測試的方法。不斷地提取指數(shù)n-1中的因子2,把n-1表示成d*2^r(其中d是一個奇數(shù))。那么我們需要計算的東西就變成了a的d*2^r次方除以n的余數(shù)。于是,a^(d * 2^(r-1))要么等于1,要么等于n-1。如果a^(d * 2^(r-1))等于1,定理繼續(xù)適用于a^(d * 2^(r-2)),這樣不斷開方開下去,直到對于某個i滿足a^(d * 2^i) mod n = n-1或者最后指數(shù)中的2用完了得到的a^d mod n=1或n-1。這樣,F(xiàn)ermat小定理加強(qiáng)為如下形式:
盡可能提取因子2,把n-1表示成d*2^r,如果n是一個素數(shù),那么或者a^d mod n=1,或者存在某個i使得a^(d*2^i) mod n=n-1 ( 0<=i<r ) (注意i可以等于0,這就把a(bǔ)^d mod n=n-1的情況統(tǒng)一到后面去了)
定理:若n是素數(shù),a是小于n的正整數(shù),則n對以a為基的Miller測試,結(jié)果為真.
Miller測試進(jìn)行k次,將合數(shù)當(dāng)成素數(shù)處理的錯誤概率最多不會超過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程序設(shè)計有所幫助。
- 使用Python判斷質(zhì)數(shù)(素數(shù))的簡單方法講解
- Python編程判斷一個正整數(shù)是否為素數(shù)的方法
- python求素數(shù)示例分享
- Python求出0~100以內(nèi)的所有素數(shù)
- python判斷所輸入的任意一個正整數(shù)是否為素數(shù)的兩種方法
- Python 判斷是否為質(zhì)數(shù)或素數(shù)的實例
- Python實現(xiàn)輸出某區(qū)間范圍內(nèi)全部素數(shù)的方法
- Python numpy.array()生成相同元素數(shù)組的示例
- python素數(shù)篩選法淺析
- Python求區(qū)間正整數(shù)內(nèi)所有素數(shù)之和的方法實例
相關(guān)文章
python使用dabl幾行代碼實現(xiàn)數(shù)據(jù)處理分析及ML自動化
這篇文章主要為大家分享一個名為?dabl?的開源?Python?工具包,它可以自動化機(jī)器學(xué)習(xí)模型開發(fā),包括數(shù)據(jù)預(yù)處理、特征可視化和分析、建模2021-11-11Python實現(xiàn)的文軒網(wǎng)爬蟲完整示例
這篇文章主要介紹了Python實現(xiàn)的文軒網(wǎng)爬蟲,結(jié)合完整實例形式分析了Python爬蟲爬取文軒網(wǎng)圖書信息的相關(guān)操作技巧,需要的朋友可以參考下2019-05-05python3+django2開發(fā)一個簡單的人員管理系統(tǒng)過程詳解
這篇文章主要介紹了python3+django2開發(fā)一個簡單的人員管理系統(tǒng)過程詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-07-07