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

数学研发论坛

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

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

[复制链接]
发表于 2008-10-7 17:20:42 | 显示全部楼层

  1.                 __int64 r=PowModular( base[i], t, n );
  2.                 if( r==1 ) continue;
复制代码
=>

  1.                 __int64 r=PowModular( base[i], t, n );
  2.                 if( r==1 ) return false;
复制代码

这里我弄错了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-7 17:20:57 | 显示全部楼层
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-7 17:31:08 | 显示全部楼层

  1.                 for( j=0; j<s; ++j ){
  2.                         if( r==n-1 ) break;
  3.                         r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
  4.                 }
  5.                 if( j<s ) continue;

复制代码
=>

  1.                 for( j=0; j<s; ++j ){
  2.                         if( r==n-1 ) break;
  3.                         r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
  4.                 }
  5.                 if( j<s-1 ) continue;
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-7 19:05:38 | 显示全部楼层
我按mathe的改了,还是不对啊.
结果还是有20个在10^16内误判了为素数.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-7 21:23:06 | 显示全部楼层

回复 24# mathe 的帖子

我感觉原代码没有问题。

但如果将:

  1.                 if( r==1 ) continue;
  2.                 int j;
  3.                 for( j=0; j<s; ++j ){
  4.                         if( r==n-1 ) break;
  5.                         r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
  6.                 }
  7.                 if( j<s ) continue;
  8.                 return false;
复制代码
替换成:

  1.                 if( r==1 || r==n-1 ) continue;
  2.                 int j;
  3.                 for( j=1; j<s; ++j ){
  4.                         r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
  5.                         if( r==n-1 ) break;
  6.                 }
  7.                 if( j==s ) return false;
复制代码
则更容易理解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-7 21:32:41 | 显示全部楼层
669094855201 = 578401*1156801,
而该数确实通过了 测试基(2, 3, 7, 61, 24251)!

这说明 Greathouse 的结论有问题,
因为该结论被许多知名站点引用,如 http://primes.utm.edu/prove/prove2_3.html
我在开发 HugeCalc 时也采信了它,现在看来有些问题了,
好在是 10^12 ~ 10^16 范围内素数很少利用到,所以影响面相对比较小。
(幸亏在前不久开发的DSP RSA中不存在该问题,因为不必要利用该结论)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-7 21:35:39 | 显示全部楼层


看来我帖子问题终于有了实际意义了啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-7 21:36:14 | 显示全部楼层
而该数确实通过了 测试基(2, 3, 7, 61, 24251)!
================================
GxQ为什么这么肯定?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-7 21:46:25 | 显示全部楼层
669094855201
20909214225
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-7 21:48:49 | 显示全部楼层
知道了。笔算验证。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2017-7-25 08:38 , Processed in 0.207016 second(s), 19 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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