[数学]CSDN上一篇关于素数判定的文章

soloforce · 发表于 2006-8-11 00:59:52

挺有意思的。最后提到了常见的米勒-拉宾（Miller-Rabin）测试
http://community.csdn.net/Expert/TopicView3.asp?id=4841478

woolzey · 发表于 2006-8-11 02:09:06

Miller-Rabin测试现在已经算是过时了。这是一个概率性算法，它只能说一个数很大概率上是素数。不过这在实际应用中已经够了，再加上一直以来没有发现更好的算法，所以它才被广泛使用。人们一直确信素性判定是一个P问题，不过奇怪的是一直没有证明。

大约2002年的时候，也就是Miller-Rabin方法提出的10多年后，三个印度人终于提出了复杂度为P的确定性的素性测试算法。这个算法，也就是所谓的AKS算法，可以在多项式时间里确定的判断一个数是否是素数。目前几乎所有的新软件里面应该都使用了这个算法来做素性测试了，比如java。现在还去研究Miller-Rabin测试，实际的意义已经不大。

AKS算法正式发布版是：Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "

RIMES is in P." Annals of Mathematics 160(2): 781-793 (2004)
它的2002年最初版和最新修改版都可以在第一作者的主页上下载：http://www.cse.iitk.ac.in/users/manindra/publications.html

soloforce · 发表于 2006-8-11 06:55:18

Good！长见识啊，谢谢woolzey提供的信息

Iambitious · 发表于 2006-8-11 08:48:07

我记得04年媒体曾经报道过这件事情，3个印度阿三，牛阿。

chai2010 · 发表于 2006-10-30 09:02:27

Post by Lolita
挺有意思的。最后提到了常见的米勒-拉宾（Miller-Rabin）测试
http://community.csdn.net/Expert/TopicView3.asp?id=4841478

今天又学了不少东西:-)

		自动登录	找回密码
密码			注册