质数算法
有谁记得cs1102讲过的质数算法， 用加减算的。
还有， 有什么方法算出一个任意大的质数嘛？
怎么样验算一个任意大的数是不是质数， 而不受硬件限制。 （eg， 在pc上验算一个大于2^62的数）
我好像可以算出任意大的质数了， 只是没法验算~_~
还有， 有什么方法算出一个任意大的质数嘛？
怎么样验算一个任意大的数是不是质数， 而不受硬件限制。 （eg， 在pc上验算一个大于2^62的数）
我好像可以算出任意大的质数了， 只是没法验算~_~
质数算法
算了几个大数， 出现了一个不是质数
有待改进， 有兴趣的可以一起讨论
算了几个大数， 出现了一个不是质数有待改进， 有兴趣的可以一起讨论
Now the standard algorithm used in
industry is the randomized algorithm for prime
http://webster.cs.uga.edu/~boanerg/fall2001/csci6610/Randomized_Algorithms.doc
however, recently, a new algorithm proposed by an Indian professor which is a determinstic
http://www.cse.iitk.ac.in/news/primality.html
However, that new algorithm has great significance in theory, but it won't be adopted by the industry since the randomized algorithm is easier to implement and yields accpetable results nearly all the time.
You know industry differs a little bit from theory, in a sense that theory always requires preciseness while a good approximation with high efficiency is more valuable.
http://webster.cs.uga.edu/~boanerg/fall2001/csci6610/Randomized_Algorithms.doc
however, recently, a new algorithm proposed by an Indian professor which is a determinstic
http://www.cse.iitk.ac.in/news/primality.html
However, that new algorithm has great significance in theory, but it won't be adopted by the industry since the randomized algorithm is easier to implement and yields accpetable results nearly all the time.
You know industry differs a little bit from theory, in a sense that theory always requires preciseness while a good approximation with high efficiency is more valuable.
Now the standard algorithm used inindustry is the randomized algorithm for prime
http://webster.cs.uga.edu/~boanerg/fall2001/csci6610/Randomized_Algorithms.doc
however, recently, a new algorithm proposed by an Indian professor which is a determinstic
http://www.cse.iitk.ac.in/news/primality.html
However, that new algorithm has great significance in theory, but it won't be adopted by the industry since the randomized algorithm is easier to implement and yields accpetable results nearly all the time.
You know industry differs a little bit from theory, in a sense that theory always requires preciseness while a good approximation with high efficiency is more valuable.
to the industry
只好用数论证明啦 :P
要验算的话，PC应该承受不起的........
我们cryptography里讲到的primality test
只是讲了一个theorem,
if there exist solutions to ( x^2 = 1 mod p ) other than +1 or -1, then p is not a prime
具体怎么实现就没说
if there exist solutions to ( x^2 = 1 mod p ) other than +1 or -1, then p is not a prime
具体怎么实现就没说
说说我地
昨晚睡觉地时候想的， n!-1
在pc能承受的范围， 在n=9的时候出错。 ~_~
不知道为什么这样
在pc能承受的范围， 在n=9的时候出错。 ~_~
不知道为什么这样
关于验证质数
学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问题就解决啦~ 整个科学界都会为之震惊；）
关于验证质数学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问题，让远到美国的牛人都激动不已，结果他的证法是错误的，而且还不认错，哈哈
关于验证质数学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问题就解决啦~ 整个科学界都会为之震惊；）
上次有一个印度学者来NUS讲学，说判断质数是P的算法
他在几年前就研究出来了，是前几个月来NUS的。
我想问一下，你是那里看到"验证一个N-digit的整数（注意是N-digit）是不是质数是一个NP问题"的。
我想问一下，你是那里看到"验证一个N-digit的整数（注意是N-digit）是不是质数是一个NP问题"的。
上次有一个印度学者来NUS讲学，说判断质数是P的算法他在几年前就研究出来了，是前几个月来NUS的。
我想问一下，你是那里看到"验证一个N-digit的整数（注意是N-digit）是不是质数是一个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问题有个大概的了解而已：）
见第3页的问题9（甲）
第4页里他说：“……問題2,4,6,7,8,9（乙）與10皆為 NP 問題，特別是問題9之（甲），（乙），其實是一樣的問題，……” 不知道是不是我理解错了，或是那个网页早已过时：）
这学期学的GEM1517K(Mathematical thinking)要求写一个关于NP的Report。当时只是在网上找找资料，所以只对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问题有个大概的了解而已：）
呵呵，你理解错了
NP is not "NP complete"
后面不是说了吗"現在已可證明在前節中之問題，除了問題1,3,5,9 之外，全是 NP-complete 問題。"
我们通常说的NP其实是NP complete. 其实这是一种不正确的简称.
后面不是说了吗"現在已可證明在前節中之問題，除了問題1,3,5,9 之外，全是 NP-complete 問題。"
我们通常说的NP其实是NP complete. 其实这是一种不正确的简称.
呵呵，你理解错了NP is not "NP complete"
后面不是说了吗"現在已可證明在前節中之問題，除了問題1,3,5,9 之外，全是 NP-complete 問題。"
我们通常说的NP其实是NP complete. 其实这是一种不正确的简称.
我有点明白了
NP-complete是NP问题中比较“难”的问题，所以只有用polynomial时间解决NP-complete问题才能证明P=NP,而对于非NP-complete的"NP问题”，只是暂时没有找到polynomial时间的算法，即使找到了，也不能说明P=NP。问题9曾是NP问题（如文中所说），但它并不是NP-complete，所以后来虽然被印度教授解决，但不能说明P=NP。
我这样理解对吗？
我这样理解对吗？
呵呵，你理解错了NP is not "NP complete"
后面不是说了吗"現在已可證明在前節中之問題，除了問題1,3,5,9 之外，全是 NP-complete 問題。"
我们通常说的NP其实是NP complete. 其实这是一种不正确的简称.
我有点明白了
NP-complete是NP问题中比较“难”的问题，所以只有用polynomial时间解决NP-complete问题才能证明P=NP,而对于非NP-complete的"NP问题”，只是暂时没有找到polynomial时间的算法，即使找到了，也不能说明P=NP。问题9曾是NP问题（如文中所说），但它并不是NP-complete，所以后来虽然被印度教授解决，但不能说明P=NP。
我这样理解对吗？
我这样理解对吗？
我们cryptography里讲到的primality test只是讲了一个theorem,
if there exist solutions to ( x^2 = 1 mod p ) other than +1 or -1, then p is not a prime
具体怎么实现就没说
好像不对吧。。。。。。
e.g. Let p=3, then there exist x=5 such that 5^2=1(mod 3).
In this case, 5 is not +1 or -1, but p=3 is still a prime. :P
In this case, 5 is not +1 or -1, but p=3 is still a prime. :P
不知道这个方法对不对。。。
Just to find a large prime number....
Starting from 2, generate a set of subsequent numbers like this:
a1 = 2
a2 = a1 + 1
a3 = a1*a2 + 1
a4 = a1*a2*a3 + 1
.
.
.
an = a1*...*a(n-1) + 1
This set of numbers should all be primes, but it doesn't contain all the prime numbers in order.
Starting from 2, generate a set of subsequent numbers like this:
a1 = 2
a2 = a1 + 1
a3 = a1*a2 + 1
a4 = a1*a2*a3 + 1
.
.
.
an = a1*...*a(n-1) + 1
This set of numbers should all be primes, but it doesn't contain all the prime numbers in order.
华新中文网致力于为新加坡留学生、工作人士及华人同胞提供交流空间和服务平台
关于我们┊ 广告服务┊ 联系方式┊ 华新博客┊ 经典怀旧┊ 投递作品
Huasing Association 1999 - 2013
