论坛 › 算法交流 › 能通过2，3，5，7的检验的合数

mathe 发表于 2008-10-8 08:11:54

原帖由 medie2005 于 2008-10-8 07:33 发表 http://bbs.emath.ac.cn/images/common/back.gif
也是错误的!
对通过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 发表于 2008-10-8 08:20:46

刚刚验证：
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 查一下你的代码。

无心人 发表于 2008-10-8 08:23:11

:lol

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

无心人 发表于 2008-10-8 08:24:54

:)

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

medie2005 发表于 2008-10-8 08:25:13

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

mathe 发表于 2008-10-8 08:26:35

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

gxqcn 发表于 2008-10-8 08:38:31

回复 46# medie2005 的帖子

19# 代码有误：__int64 MultiModular( __int64 a, __int64 b, __int64 mod ){
      __int64 r=0, t=a%mod;
      while( b>0 ){
                if( (b&1) && (r=r+t)>mod ) r-=mod;
                if( (t<<=1)>mod )t-=mod;
                b>>=1;
      }
      return r;
}应改作：__int64 MultiModular( __int64 a, __int64 b, __int64 mod ){
      __int64 r=0, t=a%mod;
      while( b>0 ){
                if( (b&1) && (r=r+t)>=mod ) r-=mod;
                if( (t<<=1)>=mod )t-=mod;
                b>>=1;
      }
      return r;
}另，请教 medie2005，是如何确定出 ( 2, 3, 7, 179, 28087 ) 组合的？:Q:

mathe 发表于 2008-10-8 08:40:58

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

gxqcn 发表于 2008-10-8 08:47:31

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

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

mathe 发表于 2008-10-8 08:52:50

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

查看完整版本: 能通过2，3，5，7的检验的合数