求一种简单的办法快速判定一个正整数为素数求一种快速而又一种简单的办法判定一个正整数为素数
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/23 22:56:16
求一种简单的办法快速判定一个正整数为素数求一种快速而又一种简单的办法判定一个正整数为素数
求一种简单的办法快速判定一个正整数为素数
求一种快速而又一种简单的办法判定一个正整数为素数
求一种简单的办法快速判定一个正整数为素数求一种快速而又一种简单的办法判定一个正整数为素数
既快速又简单的除了用计算机应该没有了,要不科学家们怎么用了那么多年筛选法呢?看看这个吧
印度的三位计算机专家(one Professor 马宁德拉·阿格拉瓦 + two Bachelors 尼拉叶·卡雅尔和尼汀·萨克斯特纳)震惊了数学界,他们为古老的素数判定问题找到了确定的多项式算法,而且令人始料未及的是,他们的判定方法出奇地简单,简单到足以让数学家们警觉起来,启发他们重新审视许多复杂问题的解决方法.
作为除了1和自身外没有其他约数的正整数,数千年来素数一直是数论的基本构件.对于如何判定一个数是否为素数,公元前240年,希腊数学家埃拉托色尼给出了一个一直沿用到今天的方法——“筛选法”.该方法有其局限性,即随着数字的增大,筛选所耗用的时间呈指数增长.如果要判定相当大的自然数,哪怕采用最先进的计算机进行运算,计算时间比宇宙年龄都要长.因此,长期以来,数学家们一直致力于寻找的,就是在可以接受的时间内能够完成的判定方法.
在过去的几十年间,由于素数判定问题被引入了密码学领域,这方面的研究工作变得倍受关注.因为当前的因特网加密程序,主要是基于大数的素因子分解相当困难这一假定.虽然目前有一些高速程序可以给出一个大数是素数的概率,但它毕竟没有彻底解决问题.
印度理工学院计算机科学与工程学系的科学家马宁德拉·阿格拉瓦和他的两位在校本科生尼拉叶·卡雅尔和尼汀·萨克斯特纳在这方面取得了成功.
这三个人的成功主要得益于采用了崭新的思路.其他人的着眼点往往是“这个数是否是素数”,他们却另辟蹊径,将问题转化成关于待判定数的一系列小的问题或“方程”.于是,简单的算法诞生了,只需用13行便可写明.阿格拉瓦解释说：“如果某个数字使所有等式成立,那么它就是素数；否则,便不是.”
卡尔·波默朗斯是美国新泽西州贝尔实验室的素数问题专家,他评论说：“这是一个漂亮的算法,我为之高兴.同时,也很遗憾自己没找到它.他们的方法很简洁,但并不平凡.他们的工作充满智慧.”
英国沃里克大学的数学家和科普作家伊恩·斯图亚特认为,这一理论突破就其本身而言固然重要,但它给人们思路上带来的启发意义更加深远.如果采用它所蕴含的换个角度、化繁为简的思想,对于那些目前处在死胡同中的难题,科学家们也许可以找到解决办法.
因特网安全目前还未因此受到威胁.来自英国一个加密安全公司的本·哈德利说：“相对于原来的概率计算算法,新算法并没有给素因子分解提供好的算法,所以这一新突破对密码安全行业并没有太大的实际影响.”
但是,波默朗斯坚信新算法将使密码学专家担忧.他认为,既然存在简单的素数判定算法,也就很可能存在简单的素因子分解算法,只是我们还没注意到罢了.
这恐怕也正是阿格拉瓦等人研究工作的真正意义所在.两名本科生的毕业项目能产生如此重大的成果,这说明我们很可能忽略掉了更多重大数学问题的简单解答方法.波默朗斯感慨颇深地说：“这是一个提醒,原来我们非常容易忽略掉一些简单的东西.”
素数判定算法
（当且仅当n为素数时,最终输出数才为素数）
lnput：integer n>1
1.if (n is of the form a^b,b>1)output COMPOSITE;
2.R=2
3.while (r
程序解决
0