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

无心人 发表于 2010-7-14 11:34:25

呃，很多东西都忘记了，重新看了一遍
因为我想写个素性测试程序

现在我有想做10^16的spsp(2)的想法了

qianyb 发表于 2010-7-14 11:55:56

10^16的spsp(2，3)表网上已经有了，不知spsp(2）的有没有

无心人 发表于 2010-7-14 12:39:18

重新看了我找到的那个论文
关键在于如果x < 10^16是psp(2)
那么，可能存在p | x， p > 10^12
这是难于处理的

无心人 发表于 2010-7-14 14:36:34

:*-^

我有了一个新的想法
可以用四元基，此时，过滤后
仅剩的数字，完全可以用两个模数
来hash一下，那么比较的代价将
远小于一次Miller-Robin测试

无心人 发表于 2010-7-14 17:25:01

如果用(2, 3, 5, 13)测试后482个例外
25667做模，将可以完全分开，一次测试确定

无心人 发表于 2010-7-14 17:29:00

(2, 3, 5, 7)的是26759， 606整数
(2, 3, 5, 11)的是28837，569整数

无心人 发表于 2010-7-14 17:44:48

采取比较算法
(2, 3, 5, 13) 的482个整数最多10次比较，也比一次测试时间少

dianyancao 发表于 2011-3-2 03:44:43

2*3*5*7 = 210

a * 210 +r:
r = 1;
r = 11;
r = 13;
r = 17;
r = 19;
……
……

mathe 发表于 2011-3-2 08:02:04

2*3*5*7 = 210

a * 210 +r:
r = 1;
r = 11;
r = 13;
r = 17;
r = 19;
……
……
dianyancao 发表于 2011-3-2 03:44 http://bbs.emath.ac.cn/images/common/back.gif
发表自己的意见之前最好先将题目认真读一下，然后看一下人家的回复

cplayer 发表于 2012-5-27 14:38:31

这个问题好像有ppt解决了啊

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