能通过2，3，5，7的检验的合数

medie2005

对测试基(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

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

gxqcn

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

medie2005

(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

无心人

(2, 3, 5, 7, x)的测试过么？

无心人

还有，可以考虑(2, 3, t, p, q)中t > 7的情况么 首先要找(2, 3, t)失败次数少的

无心人

等我写个haskell穷举下11-89的情况 看有少于(2, 3, 5)的么？

medie2005

会很慢的哦。 2，3表有52593个。若对10^5内的t穷举，大概10000个素数，所以，对我写的miller-rabin测试代码而言，要52593秒=14.6小时，就算miller-rabin测试比我的快10倍，也要接近2小时。 我以前就对(2，3，t)进行过选优，好象没发现比(2，3，5)好的。

无心人

[(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

关于如何计算$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.