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

数学研发论坛

 找回密码
 欢迎注册

QQ登录

只需一步,快速开始

楼主: 无心人

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

[复制链接]
发表于 2008-10-8 09:10:41 | 显示全部楼层
原帖由 gxqcn 于 2008-10-8 08:20 发表
刚刚验证:
21#的数据完全正确!即( 2, 3, 7, 61, 24251 )  在10^16内发生误判121次!
35#的数据,我用( 2, 3, 7, 179, 28087 ) 测试基对给出的 38 个数据复测,仅发现其中 9 个是误判的:
请 medie2005 查一下你 ...

知道原因了,不是由于代码错误,而是medie2005用的是(2,3,5,179, 28087 )而不是(2,3,7,179, 28087 )

评分

参与人数 1鲜花 +1 收起 理由
gxqcn + 1 还真是这样,怪我不仔细。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-8 09:13:45 | 显示全部楼层


乌龙了啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-8 09:17:59 | 显示全部楼层
现在目标明确下:
范围:10^16或者2^64
1、求出通过2和3测试的强伪素数
2、以1为基础求出过2,3,5,7的强伪素数
3、求出最少例外的五元组或者6元组
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 09:19:07 | 显示全部楼层
如果medie2005引用的下述结论正确
通过以2,3为底的米勒-罗宾测试的合数的只有52593个

(其实错了也没有关系,只要知道这个数目不会太大就可以了)
我们分别以一些较小的素数为底,对这52593个合数做伪素数检验,分别根据检查结果,我们可以得到一系列长度为52593的布尔向量.
我们的任务是从它们中间挑选三个,使得它们的交集最小
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 09:22:28 | 显示全部楼层
也许我们应该将底2淘汰了,而采用3和5作为最小的两个底.(因为所有2的倍数是偶数,已经事先被淘汰了,采用3和5作为最小两个底至少可以直接将所有3和5的倍数也淘汰了)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-8 09:23:23 | 显示全部楼层


所以首先要看下
完全重新作2,3测试需要多少时间?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-8 09:24:44 | 显示全部楼层


mathe的是个好主意
但选择2还有个原因是算法简单啊
当然是必须2进制运算
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 09:26:51 | 显示全部楼层
原帖由 mathe 于 2008-10-8 09:22 发表
也许我们应该将底2淘汰了,而采用3和5作为最小的两个底.(因为所有2的倍数是偶数,已经事先被淘汰了,采用3和5作为最小两个底至少可以直接将所有3和5的倍数也淘汰了)


在模运算中,“所有2的倍数是偶数”就不见得了,应该保留。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 09:29:25 | 显示全部楼层
哎,我还是缺自信啊。
老外太让我失望了,大家互抄,跟中国也没多大的区别啊。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 09:33:04 | 显示全部楼层
原帖由 gxqcn 于 2008-10-8 09:26 发表


在模运算中,“所有2的倍数是偶数”就不见得了,应该保留。


这里同模运算没有关系. 因为一个合数如果是2的倍数,由于计算机内部表示是二进制,我们非常简单就可以判断出这个数不是素数.所以我们通常都只考虑奇素数的判断.
同样,如果一个合数为p的倍数,那么它必然无法通过以p为底的伪素数测试.所以我有上面的结论.
至于无心人说的2为底的幂运算比较特殊,这个在指数比较大的时候意义不大.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2017-3-31 04:26 , Processed in 0.462263 second(s), 27 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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