|
|
|
[合著] 网友交流:关于寻找超级大质数
[ 2008-06-08 01:34:46 ]
引言/提要:寻找千万位质数不仅仅是靠技术,也跟运气有关,建议把它作为一件长期努力的事情。科研探索就是这样,风险高,需要耐性,不用寄予太大期望,该有收获的时候自然会得到结果。
关键词:寻找大质数,梅森质数,算法优化,核心技术,核心竞争力
网友(2008-5-3):
我找到了一种算法,比梅森质数算法递增的快得多得多,而且在我能验证的范围内还没有例外。我希望和你们合作在奥运会之前冲击一下1000万位的记录。有兴趣给我回电话,或者回复本邮箱。
龙之梦工作室(2008-5-3):
我们对于快速求质数的算法很感兴趣,很高兴有爱好相同的朋友,愿闻其详,共同探讨一下。
注意到那些检测质数的概率性算法,例如米勒-罗宾测试,虽然速度很快,可以在搜索质数的过程中使用,但是在确认一个数是质数的时候,概率算法是不能作准的。必须要有确定的认证算法,例如梅森质数就有又快又确定的卢卡斯-莱默测试。因此,我们需要您具体解释一下,您用来检测质数的确定性算法是怎样的。
另外,您目前的验证范围达到了多大的数?和寻找梅森质数的算法相比,速度的快慢是怎样判断出来的?这些我们都需要了解。
寻找千万位质数不仅仅是靠技术,也跟运气有关,不必非要赶在奥运之前。我们建议把它作为一件长期努力的事情。科研探索就是这样,风险高,需要耐性,不用寄予太大期望,该有收获的时候自然会得到结果。
总之,我们可以互相详细讨论,如果您的算法足够成熟,值得用程序来实现,我们就可以把它做出来。而无论结果如何,您的热情都值得鼓励,希望能够一直保持这种钻研的积极性。
网友(2008-5-5):
我的这个想法是我在发给大学数学导师的论文中的一个分支。请看论文开篇节选!
龙之梦工作室(2008-5-5)
我们看过您的文章,大致上您能够表达清楚思路。其实您定义的n级运算,用离散数学中已有的群的概念就可以表示,如果您学过离散数学有关代数系统、群、环、域等概念和性质,大可不必创造新的表示方式。另外,据我们有限的数学知识,高次方程的根在复数范围内已经可以封闭,您所定义的运算并没有超出复数系,也就是数系实质上没有扩充。
您所提供的验证范围,还没有超出二进制32位整数,也就是C程序中一个int的取值范围。这个范围其实很小,每个学过C语言的朋友都可以编出程序来验证。而且由于运算量小,即使没有什么算法优化也可以出结果。所以这个范围的验证工作就不用依赖我们了,您可以自己编写出程序来验证的。
您用到的寻找质数方法还有很大的改进空间,因为您还没有用数学方法来论证这种方法的有效性。例如:米勒-罗宾测试就明确表示,经过多少次测试之后,一个数不是质数的概率只剩下多少。这个概率是用数学方法证明过的,尽管它不能用来确认一个质数,但是可以有效减少寻找质数的运算量。
目前的通用计算机一般是32位或64位字长,而求超过64位的质数,尤其是1000位以上的质数,就不是纯粹的程序能够胜任,甚至依赖算法优化技术也不足够。必须依靠数学方法来进行有效的推导和证明,有了数学理论的基础,计算机作为工具,最后才派上用场。您提供的方法目前没有进行过数学论证,只是提出了一种设想,那就跟碰运气差不多——在32位数之内找到的质数,也许仅仅是因为运气好,也许是因为这个数据段内的质数密度比较高而已——顺便提一下,质数的密度趋向于x/ln(x),这个质数定理已经有数学证明,我们网站上也有文章提到,您大概已经知道了吧?
所以您的方法必须要有合理的数学论证,否则就摆脱不了碰运气的处境。作为您努力方向的一个参照,我们可以看看为什么梅森质数是目前大家认可的,找到已知最大质数的最有效方法:
首先是梅森质数结构简单:2^p-1,其中p是质数,数学上已证明p不会是合数。这就意味着生成这种结构的数字比较容易,寻找起来也比较容易,用较小的质数p作为指数即可。
其次是梅森质数验证简单:卢卡斯-莱默测试。因为验证不能说这个数有百分之多少的概率是质数,必须百分百肯定。卢卡斯-莱默测试就是一个经过数学证明的算法,而且运算量相对较小,所以能够快速地验证一个形如2^p-1的数是不是质数(当然这个“快速”也是以年月来计算的)。
由此可以解释,我们之前为什么要问您:用来检测质数的确定性算法是怎样的?这是个求大质数的关键问题之一。我们先不讲千万位的质数,就讲讲二进制1000位的质数。假如您用自己的方法找到了一个1000位的二进制数,您说这是个质数。我随机抓来一个1000位数,也声称是个质数,显然我“找到”质数的速度更快。那么别人怎么承认这是质数呢?所以必须提供检测质数的方法,这个方法要大家认可,而且要足够快。
按质数的定义来检测质数,也就是穷举法一个个数地除一遍,除不尽就是质数,这种方法大家都认可,用来求32位以下的质数也没有问题。但是1000位的数怎么办?这不是足够快的方法。二进制1000位的数量级上,不借助数学方法已经行不通,至于十进制千万位的质数就更不用说。在寻找梅森质数的GIMPS项目中,诸如快速傅立叶变换之类的数学算法就象吃生菜一样常见。
总而言之,在寻找大质数的道路上,你还需要付出很大的努力,有很多欠缺的东西需要弥补,不要低估了其中的难度。不过,有志者事竟成,我们觉得把它作为业余爱好就不错。追求真理是我们人类的一种美德,对不对?
顺便提一下,发邮件如果能够用文字说清楚,请尽量发txt格式的文本给我们,否则我们为了打开doc、图片之类的附件,每次都不得不先备份虚拟机快照,打开看完之后还得恢复快照备份,比较麻烦。
归纳起来,您要寻找大质数,不论我们是否参与,您都需要首先做好的:一、在32位数的范围内,自编程序验证您的方法的有效性。二、为这种方法找到合理的数学论证,表明它能够快速找到大的质数(二进制1000位以上)。三、对于找出来的数(二进制1000位以上),提供快速的确定性算法,证明它是质数。四、把方法推广到十进制千万位级别,这需要更加快速的算法。
您至少要做到了前三点,算法思路才能够说是比较成熟,我们才有机会参与进来,共同努力达到第四步——从一千到一千万。
祝您成功!
(为保护隐私,对网友身份信息作了保密处理。)
|
|
|
相关文章:
[合著] 网友交流:关于信息安全保护与成本问题 [2008-08-06] [合著] 网友交流:关于“雅典娜”网页密码锁如何保护收费网站 [2008-03-11] [转载] 管理者的三大悲哀 [2008-03-06] [合著] 网友交流:关于“雅典娜”网页密码锁 [2008-01-26] [合著] 网友交流:关于数据压缩算法 [2008-08-10] [原创] 电脑的奥林匹克:Super Prime五项测试的并行算法优化 [2008-08-31]
最新留言:
[2014-10-16] [2014-10-16] [2014-06-04] [2014-06-04] [2013-12-08] [2013-11-29]
|
|
相关链接 |
|