质数算法
登录 | 论坛导航 -> 华新鲜事 -> 社会百科 | 本帖共有 17 楼,当前显示第 10 楼 : 从楼主开始阅读 : 本帖树形列表 : 返回上一页
作者:请走人行道 (等级:6 - 驾轻就熟,发帖:4736) 发表:2003-04-26 19:37:40  10楼 
关于验证质数学CS1101S的时候,讲过两种testing的方法,一种是loop寻找n的smalleset divisors,时间是O(√n),另一种是费马小定理的逆命题来验证(Fermat's test)。 费马小定理是说:对于任何一个质数p,和一个小于p的正整数a,a^(p-1)≡1(mod p)。用这个定理的逆命题来验证n是不是质数,算法是随机取几个a,如果a^(p-1)≡1(mod p)都成立,测试就通过了。尽管Fermat's test的时间是O(logn),非常之快,但这个测试只能说明n很有可能是个质数,这是因为有些和数像561,1105也能顺利通过测试。所以这个Fermat test不能保证准确性。 (其上详情见CS1101S教材:http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.6) 据我所知,验证一个N-digit的整数(注意是N-digit)是不是质数是一个NP问题,也就是说,目前还没人能找到一个polynomial时间的算法(比如O(N^2)之类),如果真有那么一个算法,那P=NP问题就解决啦~ 整个科学界都会为之震惊;)
几年前复旦一个教授(不是计算机系的)声称解决了
P=NP问题,让远到美国的牛人都激动不已,结果他的证法是错误的,而且还不认错,哈哈
Put your OWN COOL signature here!
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版只看此人从这里展开收起列表

本帖共有 17 楼,当前显示第 10 楼,本文还有 N-1 层楼,要不你试试看:点击此处阅读更多 >>



请登录后回复:帐号   密码