二次基伪素数与素性判定

只是呼吸

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

只是呼吸

我在21楼的那个原文有一处错了。是这样写的：（其中，n-1=2^s*d,d为奇数）为基2的“强伪质数”（或“强拟质数”）。另外，那个大写的Ｎ应该是小写。我个人的看法就是把n-1分解为2的s次幂和一个奇数d的乘积。