能通过2，3，5，7的检验的合数

mathe

2. __int64 r=PowModular( base[i], t, n );
3. if( r==1 ) continue;

复制代码

=>

2. __int64 r=PowModular( base[i], t, n );
3. if( r==1 ) return false;

复制代码

这里我弄错了

medie2005

GxQ顺便给我测一下下面这几个五元组测试基吧。 (2,3,5,1151,112327) 48 fail (2,3,5,557,46853) 45 fail (2,3,5,557,161333) 44 fail (2,3,5,557,566149) 41 fail (2,3,5,179,28087) 38 fail

mathe

2. for( j=0; j<s; ++j ){
3. if( r==n-1 ) break;
4. r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
5. }
6. if( j<s ) continue;

复制代码

=>

2. for( j=0; j<s; ++j ){
3. if( r==n-1 ) break;
4. r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
5. }
6. if( j<s-1 ) continue;

复制代码

medie2005

我按mathe的改了,还是不对啊. 结果还是有20个在10^16内误判了为素数.

gxqcn

我感觉原代码没有问题。 但如果将：

2. if( r==1 ) continue;
3. int j;
4. for( j=0; j<s; ++j ){
5. if( r==n-1 ) break;
6. r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
7. }
8. if( j<s ) continue;
9. return false;

复制代码

替换成：

2. if( r==1 || r==n-1 ) continue;
3. int j;
4. for( j=1; j<s; ++j ){
5. r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
6. if( r==n-1 ) break;
7. }
8. if( j==s ) return false;

复制代码

则更容易理解。

gxqcn

669094855201 = 578401*1156801， 而该数确实通过了 测试基（2, 3, 7, 61, 24251）！ 这说明 Greathouse 的结论有问题， 因为该结论被许多知名站点引用，如 http://primes.utm.edu/prove/prove2_3.html， 我在开发 HugeCalc 时也采信了它，现在看来有些问题了， 好在是 10^12 ～ 10^16 范围内素数很少利用到，所以影响面相对比较小。 （幸亏在前不久开发的DSP RSA中不存在该问题，因为不必要利用该结论）

无心人

看来我帖子问题终于有了实际意义了啊

medie2005

而该数确实通过了 测试基（2, 3, 7, 61, 24251）！ ================================ GxQ为什么这么肯定？

无心人

669094855201 20909214225

medie2005

知道了。笔算验证。