__int64 r=PowModular( base, t, n );
if( r==1 ) continue;
=>
__int64 r=PowModular( base, t, n );
if( r==1 ) return false;
这里我弄错了 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
for( j=0; j<s; ++j ){
if( r==n-1 ) break;
r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
}
if( j<s ) continue;
=>
for( j=0; j<s; ++j ){
if( r==n-1 ) break;
r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
}
if( j<s-1 ) continue;
我按mathe的改了,还是不对啊.
结果还是有20个在10^16内误判了为素数.
回复 24# mathe 的帖子
我感觉原代码没有问题。但如果将：
if( r==1 ) continue;
int j;
for( j=0; j<s; ++j ){
if( r==n-1 ) break;
r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
}
if( j<s ) continue;
return false;
替换成：
if( r==1 || r==n-1 ) continue;
int j;
for( j=1; j<s; ++j ){
r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
if( r==n-1 ) break;
}
if( j==s ) return false;
则更容易理解。 669094855201 = 578401*1156801，
而该数确实通过了 测试基（2, 3, 7, 61, 24251）！
这说明 Greathouse 的结论有问题，
因为该结论被许多知名站点引用，如 http://primes.utm.edu/prove/prove2_3.html，
我在开发 HugeCalc 时也采信了它，现在看来有些问题了，
好在是 10^12 ～ 10^16 范围内素数很少利用到，所以影响面相对比较小。
（幸亏在前不久开发的DSP RSA中不存在该问题，因为不必要利用该结论） :)
看来我帖子问题终于有了实际意义了啊 而该数确实通过了 测试基（2, 3, 7, 61, 24251）！
================================
GxQ为什么这么肯定？ 669094855201
20909214225 知道了。笔算验证。