质数算法有谁记得cs1102讲过的质数算法， 用加减算的。

还有， 有什么方法算出一个任意大的质数嘛？

怎么样验算一个任意大的数是不是质数， 而不受硬件限制。 （eg， 在pc上验算一个大于2^62的数）

我好像可以算出任意大的质数了， 只是没法验算~_~[很硬 (4-26 3:14, Long long ago)] [ 传统版 | sForum ][登录后回复]1楼

算了几个大数， 出现了一个不是质数有待改进， 有兴趣的可以一起讨论[很硬 (4-26 3:51, Long long ago)] [ 传统版 | sForum ][登录后回复]2楼

(引用 很硬:算了几个大数， 出现了一个不是质数有待改进， 有兴趣的可以一起讨论)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.[大一的人 (4-26 7:18, Long long ago)] [ 传统版 | sForum ][登录后回复]3楼

(引用 大一的人:Now the standard algorithm used inindustry is the randomized algorithm for prime http://webster.cs.uga.edu/~boanerg/fall2001/cs...)to the industry[大一的人 (4-26 7:20, Long long ago)] [ 传统版 | sForum ][登录后回复]4楼

只好用数论证明啦 :P要验算的话，PC应该承受不起的........[有话想说 (4-26 11:35, Long long ago)] [ 传统版 | sForum ][登录后回复]5楼

我们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
具体怎么实现就没说[请走人行道 (4-26 11:58, Long long ago)] [ 传统版 | sForum ][登录后回复]6楼

说说我地昨晚睡觉地时候想的， n!-1

在pc能承受的范围， 在n=9的时候出错。 ~_~

不知道为什么这样[很硬 (4-26 13:28, Long long ago)] [ 传统版 | sForum ][登录后回复]7楼

(引用 很硬:说说我地昨晚睡觉地时候想的， n!-1 在pc能承受的范围， 在n=9的时候出错。 ~_~ 不知道为什么这样)我是想照这样算下去很有可能找到一个很大的质数不知道对不对 [很硬 (4-26 13:39, Long long ago)] [ 传统版 | sForum ][登录后回复]8楼

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

[PvsNP (4-26 15:44, Long long ago)] [ 传统版 | sForum ][登录后回复]9楼

(引用 PvsNP:关于验证质数学CS1101S的时候，讲过两种testing的方法，一种是loop寻找n的smalleset divisors,时间是O(√n),另一种是费马小定理的逆命题�...)几年前复旦一个教授（不是计算机系的）声称解决了P=NP问题，让远到美国的牛人都激动不已，结果他的证法是错误的，而且还不认错，哈哈[请走人行道 (4-26 19:37, Long long ago)] [ 传统版 | sForum ][登录后回复]10楼

(引用 PvsNP:关于验证质数学CS1101S的时候，讲过两种testing的方法，一种是loop寻找n的smalleset divisors,时间是O(√n),另一种是费马小定理的逆命题�...)上次有一个印度学者来NUS讲学，说判断质数是P的算法他在几年前就研究出来了，是前几个月来NUS的。

我想问一下，你是那里看到"验证一个N-digit的整数（注意是N-digit）是不是质数是一个NP问题"的。[吴永铮 (4-26 21:09, Long long ago)] [ 传统版 | sForum ][登录后回复]11楼

(引用 吴永铮:上次有一个印度学者来NUS讲学，说判断质数是P的算法他在几年前就研究出来了，是前几个月来NUS的。 我想问一下，你是那里看到"验证一个N-...)在一篇文章里看到的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问题有个大概的了解而已：）[PvsNP (4-26 22:17, Long long ago)] [ 传统版 | sForum ][登录后回复]12楼

(引用 PvsNP:在一篇文章里看到的http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/index.html 见第3页的问题9（甲） 第4页里他说：“……問題2,...)呵呵，你理解错了NP is not "NP complete"
后面不是说了吗"現在已可證明在前節中之問題，除了問題1,3,5,9 之外，全是 NP-complete 問題。"

我们通常说的NP其实是NP complete. 其实这是一种不正确的简称.[吴永铮 (4-26 22:36, Long long ago)] [ 传统版 | sForum ][登录后回复]13楼

(引用 吴永铮:呵呵，你理解错了NP is not "NP complete" 后面不是说了吗"現在已可證明在前節中之問題，除了問題1,3,5,9 之外，全是 NP-complete 問題。...)我有点明白了NP-complete是NP问题中比较“难”的问题，所以只有用polynomial时间解决NP-complete问题才能证明P=NP,而对于非NP-complete的"NP问题”，只是暂时没有找到polynomial时间的算法，即使找到了，也不能说明P=NP。问题9曾是NP问题（如文中所说），但它并不是NP-complete，所以后来虽然被印度教授解决，但不能说明P=NP。

我这样理解对吗？
[PvsNP (4-26 23:18, Long long ago)] [ 传统版 | sForum ][登录后回复]14楼

(引用 吴永铮:呵呵，你理解错了NP is not "NP complete" 后面不是说了吗"現在已可證明在前節中之問題，除了問題1,3,5,9 之外，全是 NP-complete 問題。...)我有点明白了NP-complete是NP问题中比较“难”的问题，所以只有用polynomial时间解决NP-complete问题才能证明P=NP,而对于非NP-complete的"NP问题”，只是暂时没有找到polynomial时间的算法，即使找到了，也不能说明P=NP。问题9曾是NP问题（如文中所说），但它并不是NP-complete，所以后来虽然被印度教授解决，但不能说明P=NP。

我这样理解对吗？
[PvsNP (4-26 23:18, Long long ago)] [ 传统版 | sForum ][登录后回复]15楼

(引用 请走人行道:我们cryptography里讲到的primality test只是讲了一个theorem, if there exist solutions to ( x^2 = 1 mod p ) other than +1 or -1, th...)好像不对吧。。。。。。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[nomore (4-27 15:29, Long long ago)] [ 传统版 | sForum ][登录后回复]16楼

不知道这个方法对不对。。。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.[nomore (4-27 15:55, Long long ago)] [ 传统版 | sForum ][登录后回复]17楼