1# wsc810
要搞素数的确定性证明，很不容易啊。我这里有一个资料，是颜松远教授的一本书上写的。
大家可以看一下，和我们现在的差距有多大。
我把他写的原文附在下面：
将Lucas数u_n定义成u_n=(a^k-b^k)/(a-b),其中，a和b为x^2-Ax+B=0之根，称奇合数n(其中，n-1=2^d,d为奇数）为基2的“强伪质数”（或“强拟质数”），如果它满足A^d-=1(mod n)或者满足A^(d*(2^r))-=-1(mod n),0<=r<s.找出这样的一个合数n,使其最后一个十进制位或者是5或者是7，并且n 是基2的“强伪质数”，同时n还必须能够整除Lucas数u_(n+1).
你要能找到这样一个合数，美国3位著名数学家Pomerance,Selfridge和Wagstaff将奖励你620美元，（这个问题在质性判定和密码学中有重要应用，计算机代数系统Maple的质性检验就是基于组合应用Miller-Rabin和Lucas这两个概率检验方法的。该组合方法自1980年提出至今，还没有发现一个反例。如果该合数存在的话，它至少具有数百个十进制位。）
以上是颜松远教授的原文。（颜松远：江西吉安人，毕业于中国科学院研究生院，获理学硕士学位，并在英国York大学数学系获得数论专业博士学位，先后在英、美等多所大学从事科研和教学工作，长期从事数论、计算理论、算法分析设计、密码学和信息安全等方面的研究与教学工作，在国际著名出版社Springer出版过三本专著）
本帖最后由 只是呼吸 于 2013-3-31 15:44 编辑
我在21楼的那个原文有一处错了。是这样写的：（其中，n-1=2^s*d,d为奇数）为基2的“强伪质数”（或“强拟质数”）。另外，那个大写的Ｎ应该是小写。我个人的看法就是把n-1分解为2的s次幂和一个奇数d的乘积。