数学研发网设为首页收藏本站

数学研发论坛

 找回密码
 欢迎注册
楼主: 无心人

[讨论] 能通过2,3,5,7的检验的合数

[复制链接]
发表于 2008-10-8 08:11:54 | 显示全部楼层
原帖由 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为底就通过不了了.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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 | 显示全部楼层


那现在我们是否有理由怀疑
2,3的那个表也存在问题呢????
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-8 08:24:54 | 显示全部楼层


media2005的代码中的模算法我觉得需要仔细测试下
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 08:25:13 | 显示全部楼层
强伪素数的定义是统一的,应当没有问题。
呵呵,回楼上,我的代码的问题我检查不出来啊,大家帮帮忙。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 08:26:35 | 显示全部楼层
所有应该完全自己检验一次
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 08:38:31 | 显示全部楼层

回复 46# medie2005 的帖子

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 ) 组合的?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 08:40:58 | 显示全部楼层
gxqcn上面指出的问题我也发现了.
另外还看出medie2005的代码要求mod最多62比特,不然r=r+t或t<<=1有可能溢出
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 08:47:31 | 显示全部楼层
10^16 仅 54 比特,所以可以放心使用。

另,指数运算应从左至右扫描,效率更高些。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 08:52:50 | 显示全部楼层
但是其实上面那个>应该改为>=也不是大问题,因为我们最终只需要判断结果是否为1和n-1
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号  

GMT+8, 2017-9-23 10:06 , Processed in 0.268252 second(s), 21 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表