素数检测算法

所需积分/C币:10 2019-07-02 17:15:47 464KB PDF
15
收藏 收藏
举报

素数的检测算 法是很有趣的,并且会涉及到数论、概率算法等诸多内容,一直觉得素数探测算法是了解概率算法很好的入口。本文和 大家简单聊聊如何确定一个数是素数。
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

...展开详情
试读 4P 素数检测算法
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 分享王者

关注 私信
上传资源赚钱or赚积分
最新推荐
素数检测算法 10积分/C币 立即下载
1/4
素数检测算法第1页

试读结束, 可继续读1页

10积分/C币 立即下载