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

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

原帖由 medie2005 于 2008-10-8 17:32 发表 http://bbs.emath.ac.cn/images/common/back.gif
现在发现形如(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很不错.大家可以过去看看,有什么好东西可以翻译过来:lol
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内的那个表发上来作为参考

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