关于验证质数
学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，和一个小于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问题就解决啦~ 整个科学界都会为之震惊；）
Huasing Association 1999 - 2013