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

mathe

原帖由 gxqcn 于 2008-10-8 08:20 发表
刚刚验证：
21#的数据完全正确！即( 2, 3, 7, 61, 24251 )  在10^16内发生误判121次！
35#的数据，我用( 2, 3, 7, 179, 28087 ) 测试基对给出的 38 个数据复测，仅发现其中 9 个是误判的：
请 medie2005 查一下你 ...

知道原因了,不是由于代码错误,而是medie2005用的是(2,3,5,179, 28087 )而不是(2,3,7,179, 28087 )

无心人

乌龙了啊

无心人

现在目标明确下：
范围：10^16或者2^64
1、求出通过2和3测试的强伪素数
2、以1为基础求出过2，3，5，7的强伪素数
3、求出最少例外的五元组或者6元组

mathe

如果medie2005引用的下述结论正确

通过以2，3为底的米勒-罗宾测试的合数的只有52593个

(其实错了也没有关系,只要知道这个数目不会太大就可以了)
我们分别以一些较小的素数为底,对这52593个合数做伪素数检验,分别根据检查结果,我们可以得到一系列长度为52593的布尔向量.
我们的任务是从它们中间挑选三个,使得它们的交集最小

mathe

也许我们应该将底2淘汰了,而采用3和5作为最小的两个底.(因为所有2的倍数是偶数,已经事先被淘汰了,采用3和5作为最小两个底至少可以直接将所有3和5的倍数也淘汰了)

无心人

所以首先要看下
完全重新作2，3测试需要多少时间？

无心人

mathe的是个好主意
但选择2还有个原因是算法简单啊
当然是必须2进制运算

gxqcn

原帖由 mathe 于 2008-10-8 09:22 发表
也许我们应该将底2淘汰了,而采用3和5作为最小的两个底.(因为所有2的倍数是偶数,已经事先被淘汰了,采用3和5作为最小两个底至少可以直接将所有3和5的倍数也淘汰了)

在模运算中，“所有2的倍数是偶数”就不见得了，应该保留。

medie2005

哎，我还是缺自信啊。
老外太让我失望了，大家互抄，跟中国也没多大的区别啊。

mathe

原帖由 gxqcn 于 2008-10-8 09:26 发表


在模运算中，“所有2的倍数是偶数”就不见得了，应该保留。

这里同模运算没有关系. 因为一个合数如果是2的倍数,由于计算机内部表示是二进制,我们非常简单就可以判断出这个数不是素数.所以我们通常都只考虑奇素数的判断.
同样,如果一个合数为p的倍数,那么它必然无法通过以p为底的伪素数测试.所以我有上面的结论.
至于无心人说的2为底的幂运算比较特殊,这个在指数比较大的时候意义不大.