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

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

[复制链接]
发表于 2008-10-11 15:37:22 | 显示全部楼层
由此,我们还是可以以搜索卡米切尔数的代码:http://bbs.emath.ac.cn/viewthrea ... ;fromuid=20#pid2131 为基础。只是这里我们有了一个优势,我们可以事先将所有素数分别根据2和3关于它们次数中2的次数分类;只有在两个分类都在一起的那些素数才允许相乘,这样应该可以降低一些复杂度。
但是卡米切尔数的代码中那些$phi(p)=p-1$需要被$phi_{2,3}(p)=LCM(phi_2(p),phi_3(p))$来代替,其中$phi_2(p)$和$phi_3(p)$分别指2和3关于素数p的次数,显然这个数不大于$phi(p)$;而这个部分会导致程序速度比那里慢一些。但是我认为通常$phi_{2,3}(p)$会等于$phi(p)$,所以这里的速度损失应该不大。总体上程序应该比卡米切尔的还要快一些。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-11 15:46:34 | 显示全部楼层
难处理的是双大因子合数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-11 16:36:39 | 显示全部楼层
10000内素数筛选(2,3)的那个表按通过后表长度倒序排列
前面是素数,后面是表长度

7对应的最多
最少几个
(3307,5190),(1117,5182),(61,5168),(13,4884),(5,4603)

l10000.txt (14.19 KB, 下载次数: 0)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-11 16:47:00 | 显示全部楼层
过(2,3,5,13)的482个

t23513.txt (7.7 KB, 下载次数: 1)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-11 16:50:39 | 显示全部楼层
原帖由 无心人 于 2008-10-11 15:46 发表
难处理的是双大因子合数

这个好处理,通过中国剩余定理。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-11 16:51:19 | 显示全部楼层
过(2,3,5,13,61)的57个
说明,单纯选最少的几个效果不好
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-11 17:01:24 | 显示全部楼层


肚子不会不知道有多少候选素数吧?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-11 17:09:55 | 显示全部楼层
你是说候选伪素数?不知道多少,但是显然挺多的。
不过卡米切尔数的题目可以在3分钟解决到$10^12$,所以如果多花些时间,这个题目解决到$10^16$还是有可能的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-11 17:17:04 | 显示全部楼层
对测试基(2,3,5,p,q),已经对p,q在10^6内的素数值进行了穷举,得到的结果是:
find a better base 13, 31249 fail 39 times
find a better base 13, 439883 fail 38 times
find a better base 13, 450817 fail 34 times
find a better base 569, 655693 fail 33 times
find a better base 1747, 16519 fail 32 times
find a better base 4057, 696811 fail 30 times
也就是说,当素数表为10^6内时,形如(2,3,5,p,q)的测试基中,最好的是(2,3,5,4057,696811).
这30次误判分别发生在:
1 : 591090138721
2 : 688529415421
3 : 4729662293401
4 : 8649193274551
5 : 34477679139751
6 : 46856248255981
7 : 133157319632851
8 : 153329903387347
9 : 363648418469461
10 : 389503070897221
11 : 583614097586281
12 : 1266147415982707
13 : 1299098974033981
14 : 1406721084285529
15 : 1584266373273781
16 : 1595200878550261
17 : 1806247902316861
18 : 2416612633262101
19 : 2419099357968541
20 : 2818290089448541
21 : 2966288653917847
22 : 3148220891032381
23 : 3533364723868561
24 : 5615477642184301
25 : 6506333961452821
26 : 6576532224211951
27 : 7024865535814141
28 : 7671546758409661
29 : 8723022119133121
30 : 9471030677258041

评分

参与人数 1威望 +2 金币 +10 贡献 +2 鲜花 +10 收起 理由
mathe + 2 + 10 + 2 + 10 精彩绝伦

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-11 17:21:51 | 显示全部楼层
对测试基(2,3,11,p,q),已经对p,q在10^5内的素数值进行了穷举,得到的结果是:
很遗憾,在10^16范围内,竟然没有一组误判次数在40次以下!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 21:44 , Processed in 0.046406 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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