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

在一篇文章里看到的http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/index.html 见第3页的问题9（甲） 第4页里他说：“……問題2,4,6,7,8,9（乙）與10皆為 NP 問題，特別是問題9之（甲），（乙），其實是一樣的問題，……” 不知道是不是我理解错了，或是那个网页早已过时：） 这学期学的GEM1517K(Mathematical thinking)要求写一个关于NP的Report。当时只是在网上找找资料，所以只对NP问题有个大概的了解而已：）