龙之梦工作室
LOGO

技术文章


(SCI) Parallel Algorithm for Wireless Data Compression and Encryption   (SCI) Fast Algorithm of Truncated BWT for Data Compression of Sensors   Dr. Qin Jiancheng   龙之梦助力肇庆教育网云计算   Dr. Zhou Yousheng   Dr. Bai Yuan   龙之梦工作室加盟华南理工学术团队   [软件下载] ComZip超级压缩机免费版下载   继续潜行,龙之梦工作室技术研发又一年   [软件交易] “雅典娜”网页密码锁在线购买   [软件交易] Super Prime超级质数机在线购买   [软件交易] ComZip超级压缩机在线购买   [信息安全] “风语者”高强度加密技术   [信息安全] 多层纵深防御体系结构   [合著] 专利:安全事件检测方法及装置  

[合著] 网友交流:关于寻找超级大质数

[ 2008-06-08 01:34:46 ]

  引言/提要:寻找千万位质数不仅仅是靠技术,也跟运气有关,建议把它作为一件长期努力的事情。科研探索就是这样,风险高,需要耐性,不用寄予太大期望,该有收获的时候自然会得到结果。

  关键词:寻找大质数,梅森质数,算法优化,核心技术,核心竞争力

Super Prime 超级质数机

网友(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]


从2005年3月18日起
访问本站页面计数器人次
版权所有 © 2005 龙之梦工作室,保留一切权利。
电子邮箱:master@28x28.com , co2288@126.com
相关链接 |