开发工具:
文件大小: 464kb
下载次数: 0
上传时间: 2019-07-02
详细说明：素数的检测算 法是很有趣的，并且会涉及到数论、概率算法等诸多内容，一直觉得素数探测算法是了解概率算法很好的入口。本文和 大家简单聊聊如何确定一个数是素数。7. if p bing==1
8. result result a %o m
9.
10. return result
这个算法的复杂度正比于a、p和m中位数最多的数的二进制位数,要远远低于朴素的模幂求解法
例如,下面的代码在我的机器上瞬间可以完成
1. compute power(2,
6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977
296311391480858037121987999716643812574028291115057150
6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977
296311391480858037121987999716643812574028291115057151)
而用直观方法计算如此大指数的幂基本是不可能的
费马检测的实现
有了上的铺垫,下面可以实现费马检测了
1. def prime test fermat(p)
2.ifp==1
3. return False
4.ifp==2
5. return True
6. d= compute power(2, p-1, p)
7.d==1:
8. return True
9. return False
以下是一些测试
1. print prime test fermat(7)#True
2. print prime test fermat(11)#True
3. print prime test fermat(15)#False
4. print prime test fermat(121)#False
5. print prime test fermat(561)#True
6. print
prime test fermat(6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559
640661454554977296311391480858037121987999716643812574028291116057151)#True
需要注意的是,倒数第二个结果实际是错的,因为561可以分解为3和187。
相对来说,因子分解法适合比较小的数的探测,可以给出准确的结论,但是对于大整数效率不可接受,例如上面最后一
个超大整数,因子分解法基本不可行;费马测试当给出否定结论时,是准确的,但是肯定结论有可能是错误的,对于大
整数的效率很高,并且误判率随着整数的增大而降低
Ml|ler- Rabin检测
上文说,费马检测失误的概率随着整数不断増大而趋向于0,看似是对大素数检测很好的算法。那么我们考虑另外一个问
题:如果一个数p是合数,a是小于p的正整数且a不满足费马定理公式,那么a叫做p是合数的—个证据,问题是,对于任
意一个合数p,是否总存在证据?
答案是否定的。例如561这个数,可以分解为3乘以187,但是如果你试过会发现所有小于561的正整数均符合费马定理公
式。这就意味着,費马检测对于561是完全失效的。类似561这样是合数但是可以完全欺骗費马检测的数叫做 Carmichae
数。 Carmichae数虽然密度不大(前10亿个正整数中约600个),但是已经被证明有无穷多个。 Carmichael数的存在迫使
需要一种更强的检测条件配合单纯费马检测使用,其中 Miller-Rabin检测是目前应用比较广泛的一种。
Miller-Rabn检测依赖以下定理
如果p是素数,x是小于p的正整数,且x2=1modp,则x要么为1,要么为p-1。
简单证明:如果x^2=1mdp;则p整除x^2-1,即整除(x+1)(x-1),由于p是素数,所以p要么整除x+1,要么整除x-1
前者则x为p-1,后者则x为1
以上定理说明,如果对于任意一个小于p的正整数x,发现1(模p)的非平凡平方根存在,则说明p是合数。
对于p-1,我们总可以将其表示为u2^t,其中u是奇数,t是正整数。此时
ap-1=a u2 t=(au)2 t
也就是可以通过先算出a~u,然后经过连续次平方计算出a^(p-1),并且,在任意一次平方时发现了非平凡平方根,则断
定p是合数。
例如,560=35*2^4,所以可设u=35,t=4
23526321662672mod561=263mod561=166mod561=67mod561=1
由于找到了—个非平凡平方根67,所以可以断言561是合数。因此2就成为了561是合数的一个证据
一般的, Miller-Rabin算法的 python实现如下
1. def miller_ rabin_ witness(a, p)
2.ifp==1:
3. return False
4. if p==2
5. return True
6.
7.n=p-1
8. t=int(floor(log(n, 2)))
9.u=1
10. while t>0
11.u=n/2*t
12.计n%2*t==0andu%2==1
13 break
14.t=t-1
15
16. b1=b2=compute_power(a, u, p)
17. for i in range(1, t+ 1)
18.b2=612%p
19. if b2==1 and b1 1=1 and b1 l=(p-1)
20. return False
21.b1=b2
22.ib11=1:
23. return False
24.
25. return True
26.
27. def prime test miller rabin(p, k)
28. while>0
29. a= randint(1, p-1)
30. if not miller rabin witness(a, p)
31. return False
32.k=k-1
33. return True
其中 miller rabin witnes用于确认a是否为p为合数的证据, prime test miller rabin共探测k次,每次随机产生一个1至p
1间的整数。只要有一次发珈p为合数的证据就认为p为合数,否则认为p为素数。一些测试
1. print prime test miller rabin(7, 5)#True
2. print prime test miller rabin(21, 5)#False
3. print prime test_ miller_ rabin(561, 50)#False
4. print
prime test miller rabin(686479766013060971498190079908139321726943530014330540939446345918554318339765605212
2559640661454554977296311391480858037121987999716643812574028291115057151,50)#TUe
Miller-Rabin检测也同样存在假阳性的问题,但是与费马检测不同,MR检测的正确概率不依赖被检测数p(排除了
Carmichae数失效问题),而仅依赖于检测次数。已经证明,如果一个数p为合数,那么 Miller-Rabin检测的证据数量不少
于比其小的正整数的314,换言之,k次检测后得到错误结果的概率为(14)~k,例如上面最后一个大整数, Miller-Rabin检
测认为其实素数,我设k为50,也就是说它被误认为素数的概率为(14)^50。这个概率有多小呢,小到你不可想象。直观
来说,大约等于一个人连续中得5次双色球头奖的概率。
参考文献
[1]算法导论
[2]http://www.wikipedia.org
3]http://www.matrix67.com/blag/archives/234
「4]http://www.bigprimes.net
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
