能通过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