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

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

[复制链接]
发表于 2008-10-11 07:10:33 | 显示全部楼层
对测试基(2,3,5,p,q),已经对p,q在10^5内的素数值进行了穷举,得到的结果是:
find a better base 13, 31249 : fail 39 times
find a better base 179, 28087 : fail 38 times
find a better base 569, 49037 : fail 36 times
find a better base 1747, 16519 : fail 32 times
也就是说,当素数表为10^5内时,形如(2,3,5,p,q)的测试基中,最好的是(2,3,5,1747,16519).

[ 本帖最后由 medie2005 于 2008-10-11 07:35 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-11 07:42:16 | 显示全部楼层
对测试基(2,3,7,p,q),已经对p,q在10^5内的素数值进行了穷举,得到的结果是:
很遗憾,在10^16范围内,竟然没有一组误判次数在40次以下!
所以,可以说(2,3,7,p,q)的组合是不优秀的.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-11 07:59:42 | 显示全部楼层

回复 132# medie2005 的帖子

可否把 (2,3,5,1747,16519) fail 的清单列出来?
我再复测一下。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-11 08:24:26 | 显示全部楼层
(2,3,5,1747,16519) fail 的清单:
4341937413061
15866254242541
24763294876321
45205022555551
321692680511281
389503070897221
416841276847141
455619077459281
493813961816587
737673272719951
974127971403361
1583435793635011
2215343259547651
2342879850289441
2962600060014181
3097843114460221
3330327948852061
3375024351663361
3915200777835007
4066010727465781
4498414682539051
5432805495506161
6830509209595831
6954068117507941
7066336659681601
7146129240985351
8294034991343221
8411071134570301
8945906453479621
9048975139025251
9578118265649251
9811179695712397

评分

参与人数 1贡献 +2 鲜花 +1 收起 理由
gxqcn + 2 + 1 经复测,正确!

查看全部评分

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


(2, 3, 5, 7, x)的测试过么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-11 09:10:49 | 显示全部楼层
还有,可以考虑(2, 3, t, p, q)中t > 7的情况么
首先要找(2, 3, t)失败次数少的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-11 09:12:33 | 显示全部楼层
等我写个haskell穷举下11-89的情况
看有少于(2, 3, 5)的么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-11 09:40:32 | 显示全部楼层
会很慢的哦。
2,3表有52593个。若对10^5内的t穷举,大概10000个素数,所以,对我写的miller-rabin测试代码而言,要52593秒=14.6小时,就算miller-rabin测试比我的快10倍,也要接近2小时。
我以前就对(2,3,t)进行过选优,好象没发现比(2,3,5)好的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-11 14:56:41 | 显示全部楼层
[(11,5429),(13,4884),(17,5499),(19,5432),(23,5449),(29,5234),(31,5393),(37,5247)
,(41,5401),(43,5398),(47,5505),(53,5307),(59,5363),(61,5168),(67,5329),(71,5431)
,(73,5326),(79,5423),(83,5413),(89,5388),(97,5376)]

上面是对11到97的素数筛选2,3表得到的表长度
补充5,7的表长度
(5, 4603)
(7, 6071)

可以看到和素数大小关系不大
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-11 15:29:56 | 显示全部楼层
关于如何计算$10^16$(或$2^64$)以内所有以2和3为底的伪素数,我又找到一个对计算有帮助的性质。
假设N是以a为底的伪素数,其中p和q是N两个不同的素因子。假设a关于p的次数是$2^s*u$,a关于q的次数伪$2^t*v$,其中u,v为奇数。那么必然有s=t.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-19 18:55 , Processed in 0.044411 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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