米勒-罗宾算法

当前位置:beplay登录 > beplay首页 > 米勒-罗宾算法
作者: beplay登录|来源: http://www.qdgxdx.com|栏目:beplay首页

文章关键词:beplay登录,米勒

  如何判断一个素是素数,迄今为止最有效的方法是筛数法,做个表(打表法)即素数的倍数一定是合数。筛选法的效率很高,但是遇到大素

  米勒罗宾算法是一个相当著名的判断是否是素数的算法,能够很大概率的判断一个数是否是素数(接近100%,在一定范围内能达到100%)。

  如果对这个过程重复50次,每次都没说它是合数,那这个数是素数的概率是多少那?

  很显然就像是投硬币那样如果你投了1000次,每次都投到正面 ,那你就会怀疑这个硬币2面都是正面!

  米勒罗宾算法的算法很简单,但是由于需要计算a^(n-1)%n这类的问题,如果不经行优化,对于大数计算时间复杂度仍旧很高。

  把a 分解成 t个2 和 奇数u的乘积 ,比如 144 可以分解成4个2 和一个9的乘积

  1比如2个64位整数的乘积超过64位,会产生溢出。解决这个问题的方法有3个

  3)使用JAVA,Java有大数类,方便实惠!所以这次开始用c++写,后来改成了java

  3实现可以做张素数表,加速计算,我就实现打了张1900个素数的大表!大家不要鄙视打表,在计算机中很常用的。

  当然米勒罗宾算法只能判断它是否是素数,但如果知道了它不是素数后,则么样才能得到它的因数那?

  这个算法是启发式的,不一定能在有限时间内找到,需要写的很好才不会遇到偶尔死循环的情况。

  要优化可以考虑优化gcd的计算。这个算法我写的方法还有很多漏洞,相当不完善,自己功力也不够解释清楚。

下一篇:没有了

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!