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

mathe

原帖由 medie2005 于 2008-10-8 07:33 发表
也是错误的!
对通过2,3为底的miller-rabin测试的118670087467,以5,7为底的milller-rabin测试结果如下:
for base 5:
5^59335043733 mod 118670087467 == 118670087466
5^118670087466 mod 118670087467 == 1
=== ...

的确如此,我用HugeCalc下面附带的NumberTheoretic.exe进行了验算.对于低2,3,5,7.
它们的59335043733都是-1,所以通过测试.但是换成11为底就通过不了了.

gxqcn

刚刚验证：
21#的数据完全正确！即( 2, 3, 7, 61, 24251 )  在10^16内发生误判121次！
35#的数据，我用( 2, 3, 7, 179, 28087 ) 测试基对给出的 38 个数据复测，仅发现其中 9 个是误判的：

1: 1871186716981
7: 90022554326251
9: 393674060691451
12: 694647820912249
13: 697558946623951
16: 806943042831361
31: 4776659506394821
34: 6174694133111701
36: 6422257147825261

请 medie2005 查一下你的代码。

无心人

那现在我们是否有理由怀疑
2，3的那个表也存在问题呢？？？？

无心人

media2005的代码中的模算法我觉得需要仔细测试下

medie2005

强伪素数的定义是统一的，应当没有问题。
呵呵，回楼上，我的代码的问题我检查不出来啊，大家帮帮忙。

mathe

所有应该完全自己检验一次

gxqcn

19# 代码有误：

1. __int64 MultiModular( __int64 a, __int64 b, __int64 mod ){
   
2.         __int64 r=0, t=a%mod;
   
3.         while( b>0 ){
   
4.                 if( (b&1) && (r=r+t)>mod ) r-=mod;
   
5.                 if( (t<<=1)>mod )  t-=mod;
   
6.                 b>>=1;
   
7.         }
   
8.         return r;
   
9. }

复制代码

应改作：

1. __int64 MultiModular( __int64 a, __int64 b, __int64 mod ){
   
2.         __int64 r=0, t=a%mod;
   
3.         while( b>0 ){
   
4.                 if( (b&1) && (r=r+t)>=mod ) r-=mod;
   
5.                 if( (t<<=1)>=mod )  t-=mod;
   
6.                 b>>=1;
   
7.         }
   
8.         return r;
   
9. }

复制代码

另，请教 medie2005，是如何确定出 ( 2, 3, 7, 179, 28087 ) 组合的？

mathe

gxqcn上面指出的问题我也发现了.
另外还看出medie2005的代码要求mod最多62比特,不然r=r+t或t<<=1有可能溢出

gxqcn

10^16 仅 54 比特，所以可以放心使用。

另，指数运算应从左至右扫描，效率更高些。

mathe

但是其实上面那个>应该改为>=也不是大问题,因为我们最终只需要判断结果是否为1和n-1