mathe

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

复制代码

=>

1.                 __int64 r=PowModular( base[i], t, n );
   
2.                 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

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

复制代码

=>

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

复制代码

medie2005

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

gxqcn

我感觉原代码没有问题。

但如果将：

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

复制代码

替换成：

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

知道了。笔算验证。