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

mathe · 发表于 2008-10-9 07:44:05

原帖由 medie2005 于 2008-10-8 17:32 发表现在发现形如(2,3,5,x,x)的五元组测试基还是很好的，后两个测试基选得适当的话，在10^16内，一般都能小于50次误判。

是不是你已经穷举了一定范围内的(2,3,5,p,q)形式的结果

medie2005 · 发表于 2008-10-9 07:59:30

最佳只能是想象，因为素数表我只用了10^6以内的，而且也没有用穷举，只是半随机地查找。

无心人 · 发表于 2008-10-9 08:06:30

可否这么认为 1、如果一个4元组的误判少于200 2、如果一个5元组的误判少于20 就是极端优秀的现在有个问题 1、一个Miller-Rabin测试的消耗时间在一般意义上相当于多少整数的相等比较我认为至少要大于500个整数比较（假设使用32个乘法，每个乘法最少32个时钟，则1024个时钟） 2、由问题1使用较优秀的5元组是否开销小于较优秀的4元组更明确的，是否大于一般的4元组（有500个以内例外的）

medie2005 · 发表于 2008-10-9 09:11:44

4元组误判少于500的我目前只发现了一个。 5元组可能能误判少于30，但20就不好说了。

medie2005 · 发表于 2008-10-9 09:22:17

（2，3，5，239，688477 ） 37 fail （2，3，5，13） 482 fail （2，3，5，49037） 481 fail （2，3，5，72101） 478 fail （2，3，5，102199） 475 fail （2，3，5，136333） 471 fail （2，3，5，375233） 470 fail （2，3，5，61363，136333） 35 fail （2，3，5，136333，392069） 34 fail [ 本帖最后由 medie2005 于 2008-10-9 16:48 编辑 ]

无心人 · 发表于 2008-10-9 09:30:18

那考虑下一次Miller-Rabin测试的开销？

mathe · 发表于 2008-10-9 14:20:03

我找到了Greathouse在一个BBS上经常活动,给他(CRGreathouse)发了站内信告诉他这个错误了. 那个BBS很不错.大家可以过去看看,有什么好东西可以翻译过来

http://www.mymathforum.com/

无心人 · 发表于 2008-10-9 17:32:22

那里似乎流行用PARI/GP写东西呵呵用它尝试解下这个问题？

无心人 · 发表于 2008-10-9 17:36:47

PARI/GP 真妙啊可以作为一个高档计算器的呵呵

无心人 · 发表于 2008-10-9 20:19:59

把网上的基于2，3的10^16内的那个表发上来作为参考

SPSP10^16.rar (363.9 KB, 下载次数: 8)

账号		自动登录	找回密码
密码			欢迎注册

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