论坛 › 算法交流 › 能通过2，3，5，7的检验的合数

medie2005 发表于 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 编辑 ]

medie2005 发表于 2008-10-11 07:42:16

对测试基(2,3,7,p,q),已经对p,q在10^5内的素数值进行了穷举,得到的结果是:
很遗憾,在10^16范围内,竟然没有一组误判次数在40次以下!
所以,可以说(2,3,7,p,q)的组合是不优秀的.

gxqcn 发表于 2008-10-11 07:59:42

回复 132# medie2005 的帖子

可否把 (2,3,5,1747,16519) fail 的清单列出来？
我再复测一下。

medie2005 发表于 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

无心人 发表于 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)的么？

medie2005 发表于 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)

可以看到和素数大小关系不大

mathe 发表于 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.

查看完整版本: 能通过2，3，5，7的检验的合数