本文实例讲述了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, n1, 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程序设计有所帮助。
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
更新日志
- 【原神手游】5.1版本更新维护预告
- 李锦华.1987-日与夜(LP版)【SOLO】【WAV+CUE】
- 伍珂玥.2014-伍珂玥【湾彩星辰】【FLAC分轨】
- 吕方.2001-旧情人·老情歌精选2CD【华纳】【WAV+CUE】
- 《星际战士2》¥219,《100% 鲜橙汁》¥7
- 手办鉴赏室:少女眼神颇有杀意!连衣裙勾勒傲人轮廓
- 未来可期的二次元大逃杀游戏——《白厄战境》简评
- 炉石传说死亡骑士卡组怎么搭配 死亡骑士最新卡组2024推荐
- 魔兽世界地下堡珍玩怎么升级 地下堡珍玩升级方法攻略分享
- 魔兽世界怎么获得泽克维尔的残血珍玩 泽克维尔的残血珍玩获取方式
- FrankSinatra-StrangersInTheNight(1966Jazz)[Flac24-96]
- 大原樱子《CAMON+5thAnniversaryBest~》2CD[24-96]flac
- Isgaard2003-GoldenKey(LimitedEdition)【WAV+CUE】
- 《合金装备3RE》伊娃定妆照公布:没被政确太好了
- 石家庄新增《黑神话:悟空》墙绘:小狐狸萍萍