设为首页 - 加入收藏
广告 1000x90
您的当前位置:刘伯温高手论坛 > 梅森城 > 正文

如何快速检查一个素数的素性(算法)

来源:未知 编辑:admin 时间:2019-08-15

  1楼的算法太弱智了,你检测一个1024位素数你看看你要活多少年才能看到结果?要快速的,起码要在1分钟内吧!

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  本科学历,毕业后从事设计工作;现任标码石材科技有限公司设计员。能决绝结构设计方面中等难度问题。现在,确定性素数判定法已经有很多种,常用的有试除法、威廉斯方法、艾德利曼和鲁梅利法。它们的适用范围各不相同,威廉斯方法比较适合10^20到10^50之间的数,艾德利曼和鲁梅利法适合大于10^50的数,对于32位机器数,由于都小于10^10,所以一般都用试除法来判定。

  阿格拉瓦法虽然是log(n)的多项式级算法,但目前只有理论上的意义,根本无法实用,因为它的时间复杂度是O(log(n)^12),这个多项式的次数太高了。就拿最慢的试除法跟它来比吧,试除法的时间复杂度为O(n^(1/2)*log(n)^2),当n = 16时,log(n)^12 = 16777216,而n^(1/2)*log(n)^2 = 64,你看相差有多么大!如果要让两者速度相当,即log(n)^12 = n^(1/2)*log(n)^2,得出n = 10^43.1214,此时需要进行的运算次数为log(n)^12 = 10^25.873(注意:本文中log()函数缺省以2为底),这样的运算次数在一台主频3GHz的计算机上运行也要10^8.89707年才能运行完,除了这些确定性素数判定法外,还有基于概率的非确定性素数判定法,最常用的就是米勒-拉宾法。

  展开全部算好,我以前也研究过素数问题.现在资料还保存着.. 拿来给你分享吧. (这个算法检测速度,还是很快的,你可以试试看哦~~)

  本文通过对米勒-拉宾非确定性素数判定法如何转化为确定性素数判定法的研究,发现了与之相关的伪素数的一些性质,引入了伪素数的最小可判定底数的概念,并总结出了一些规律。通过这些规律找出了一种特别适合32位机器数的确定性素数判定法,该方法对于32位机器数进行素数判定最多只需要进行16log(n) 次乘/除法。该方法具有实现简单、速度快的优点,非常具有推广价值。

  本文中总结出的一些规律如果能够得到证明和推广,则有可能彻底解决把米勒-拉宾非确定性素数判定法转化为确定性素数判定法的问题,从而对素数判定理论和实践产生一定的促进作用。

  第一章:讲述素数判定法的现状,列举了目前常用的一些素数判定法及其适用范围。

  第三章:分析伪素数表,引入了伪素数的最小可判定底数的概念,并且总结出了一些规律。根据这些规律,找出了一种特别适合32位机器数的确定性素数判定法,并且进行了多种优化,给出了时间复杂度分析。

  确定性素数判定法:一个素数判定法判定某个自然数为素数的充要条件是该自然数确实是素数,该判定法就是确定性素数判定法。即该判定法不存在误判的可能性。

  现在,确定性素数判定法已经有很多种,常用的有试除法、威廉斯方法、艾德利曼和鲁梅利法。它们的适用范围各不相同,威廉斯方法比较适合10^20到10^50之间的数,艾德利曼和鲁梅利法适合大于10^50的数,对于32位机器数,由于都小于10^10,所以一般都用试除法来判定。

  也许有人会问:“你为什么没有提马宁德拉.阿格拉瓦法呢?不是有人说它是目前最快的素数判定法吗?” 其实这是一个很大的误解,阿格拉瓦法虽然是log(n)的多项式级算法,但目前只有理论上的意义,根本无法实用,因为它的时间复杂度是O(log(n)^12),这个多项式的次数太高了。就拿最慢的试除法跟它来比吧,试除法的时间复杂度为O(n^(1/2)*log(n)^2),当n = 16时,log(n)^12 = 16777216,而n^(1/2)*log(n)^2 = 64,你看相差有多么大!如果要让两者速度相当,即log(n)^12 = n^(1/2)*log(n)^2,得出n = 10^43.1214,此时需要进行的运算次数为log(n)^12 = 10^25.873(注意:本文中log()函数缺省以2为底),这样的运算次数在一台主频3GHz的计算机上运行也要10^8.89707年才能运行完,看来我们这辈子是别指望看到阿格拉瓦法比试除法快的这一天啦!

  除了这些确定性素数判定法外,还有基于概率的非确定性素数判定法,最常用的就是米勒-拉宾法。

  对于32位机器数(四则运算均为常数时间完成),试除法的时间复杂度是O(n^(1/2)),而米勒-拉宾法的时间复杂度只有O(log(n))。所以后者要比前者快得多,但是由于米勒-拉宾法的非确定性,往往我们在需要确定解时仍然要依靠速度较慢的试除法。那是否可以通过扩展米勒-拉宾法,来找到一种更快的确定性素数判定法呢?结论是肯定的,本文就带你一起寻找这样一种方法。

  既然要扩展米勒-拉宾法,那首先我们应该知道为什么米勒-拉宾法是个非确定性素数判定法?答案很简单,由于伪素数的存在。由于米勒-拉宾法使用费尔马小定理的逆命题进行判断,而该逆命题对极少数合数并不成立,从而产生误判,这些使费尔马小定理的逆命题不成立的合数就是伪素数。为了研究伪素数,我们首先需要生成伪素数表,原理很简单,就是先用筛法得出一定范围内的所有素数,然后逐一判定该范围内所有合数是否使以2为底数的费尔马小定理的逆命题不成立,从而得出该范围内的2-伪素数表。我的程序运行了100分钟,得出了32位机器数范围内的2-伪素数表,如下:

  对于2-伪素数表的每一个伪素数,寻找最小的可以判定它们是合数的底数,我把这个底数称之为最小可判定底数。特别地,对于绝对伪素数,它的最小质因子即是它的最小可判定底数。由于已经证明了绝对伪素数至少有三个质因子,所以这个最小质因子一定不大于n^(1/3)。下面就是我找到的最小可判定底数列表:

  通过统计这个列表,我发现了一个规律,那就是所有的最小可判定底数都不大于n^(1/3),由前述可知,对于绝对伪素数,这个结论显然成立。而对于非绝对伪素数,虽然直观上觉得它应该比绝对伪素数好判定出来,但是我无法证明出它的最小可判定底数都不大于n^(1/3)。不过没关系,这个问题就作为一个猜想留给数学家来解决吧,更重要的是我已经通过实验证明了在32位机器数范围内这个结论成立。

  我们还有没有更好的方法来进一步减小最小可判定底数的范围呢?有的!我们可以在计算平方数时进行二次检测,下面是进行了二次检测后重新计算的最小可判定底数列表:

  很显然,二次检测是有效果的,经过统计,我发现了新的规律,那就是经过二次检测后所有的最小可判定底数都不大于n^(1/6),真的是开了一个平方呀,哈哈!这个结论的数学证明仍然作为一个猜想留给数学家们吧。我把这两个猜想叫做费尔马小定理可判定上界猜想。而我已经完成了对32位机器数范围内的证明。

  通过上面总结的规律,我们已经可以设计出一个对32位机器数进行素数判定的 O(n^(1/6)*log(n)) 的确定性方法。但是这还不够,我们还可以优化,因为此时的最小可判定底数列表去重后只剩下了5个数(都是素数):{2,3,5,7,11}。天哪,就是前5个素数,这也太容易记忆了吧。

  不过在实现算法时,需要注意这些结论都是在2-伪素数表基础上得来的,也就是说不管如何对2的判定步骤必不可少,即使当2n^(1/6)时。

  还有一些优化可以使用,经过实验,当n=7^6时,可以不进行n^(1/6)上界限制,而固定地用{2,5,7,11}去判定,也是100%正确的。这样就可以把判定次数降为4次以下,而每次判定只需要进行4log(n)次乘除法(把取余运算也看作除法),所以总的计算次数不会超过16log(n)。经过实验,最大的计算次数在n=4294967291时出现,为496次。

  需要说明的一点是,虽然我在输入时使用了longlong_t,那是为了类型一致性,有效的输入范围仍然是0 ~ 2^32-1 。

  如果前述的费尔马小定理可判定上界猜想可以被证明,那么该算法可以被推广到任意位数的n,此时的时间复杂度为O(n^(1/6)*log(n)^3)。这样我们就可以完成米勒-拉宾非确定性素数判定法向确定性素数判定法的转化,这对于数论理论是一个补充,对于实践中使用米勒-拉宾素数判定法具有指导意义。

  本文所做的研究只是向米勒-拉宾非确定性素数判定法的确定化方向迈出了一小步,我相信,在不久的将来,米勒-拉宾非确定性素数判定法的确定化方向会有更大进展,从而对数论理论和实践产生深远影响。

  《计算机算法设计与分析(第2版)》,王晓东编著,电子工业出版社,2004年7月。

  如果你真的对这个又兴趣,你可以参加“因特网梅森素数大搜索”(GIMPS)活动!

  现在人们查找到的最大素数也才700位,据《新科学家》杂志网站1日报道,这位名叫约翰·芬德力的数学爱好者五年前用自己的家用台式电脑加入了 “因特网梅森素数大搜索”(GIMPS)活动,他也是用这台普通的台式机偶然间发现这个素数的。在5月30日正式向外界公布这一消息之前,他还花费了两周的时间进行验证。而另外两位身在法国和加拿大的“因特网梅森素数大搜索”活动的志愿者也证实了芬德力的发现。而就在半年前,美国的一位学生曾发现第40个梅森素数,它共有6320430位数。

  1995年,美国程序设计师乔治·沃特曼整理有关梅森素数的资料,编制了一个梅森素数计算程序,并将其放置在因特网上供数学爱好者使用,这就是 “因特网梅森素数大搜索”计划。目前有6万多名志愿者、超过20万台计算机参与这项计划。该计划采取分布式计算方式,利用大量普通计算机的闲置时间,获得相当于超级计算机的运算能力,第37、38和39个梅森素数(梅森素数是指能被2的n次方减一的素数)都是用这种方法找到的。美国一家基金会还专门设立了 10万美元的奖金,鼓励第一个找到超过千万位素数的人。

本文链接:http://qchba.com/meisencheng/922.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top