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

medie2005 · 发表于 2008-10-11 19:10:33

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

mathe · 发表于 2008-10-11 19:15:08

看规律基本上那组(2,3,5,4057,696811)最好了

medie2005 · 发表于 2008-10-11 19:19:19

是啊,如果存在(2,3,t)比(2,3,5)误判少,那么,由无心人的数据,t肯定不小,于是,这就缩小了(2,3,t,p,q)中p和q的取值范围,也减少了(2,3,t,p,q)低于30次误判的机会. 基本上,在现在我的计算能力下,找到30次误判的测试基已经是极限了.

无心人 · 发表于 2008-10-11 19:31:23

说几点我傍晚想到的 1、我的数据只考虑了10000内的情况，如果计算到100万，很遗憾，需要70多小时 2、似乎不超过100万的素数p，存在(2, 3, p)的数据在(2, 3, 5）和(2, 3, 13）之间 3、因为(2, 3, 7)的数据竟然在情况1下是最多的，是否认为，(2, 3, p)的数据的优劣和p的某种结构有关？ 4、是否认为仅仅10^ 16内的我们的这种测试代表了在广泛的数字范围内的大概趋势？或者说在10^100内，是否认为(2, 3, 5, 7, 11)并不比(2, 3, 5, 13, 61)效果好，或者说误判几率高于后者？ 5、最重要的，因为7的意料外的结果，我们是否有理由怀疑3？另外，media找到的最好的解，4057并不在我的数据的低通过率数字中，是否意味着单测试数据并不能说明通过率低的两个数字的组合的通过率一定要小于通过率高的组合

无心人 · 发表于 2008-10-11 19:47:13

PS：说点题外的话似乎64位二进制数字进行Miller-Rabin测试在2G机器上很难把总时间控制在10000时钟以x86 32位机器为例子计算下一次64乘的消耗是> 9 * 4 + 6 = 42 一次128位模64位是至少128时钟（我怎么看蒙哥马利算法在汇编级不如连续减，这里考虑的是连续减）平均需要96次乘和模运算加一次初始化一个减法的预先表需要64 * 2 = 128 则共运算128 + 96 * (128 + 42) = 16448时钟我想这个结果很难达到即随机意义下一秒能计算12万次我估计能计算到5万次就算不错了

gxqcn · 发表于 2008-10-11 20:08:24

64位二进制数字进行Miller-Rabin测试，若在64位OS下肯定比在32位系统下好。

无心人 · 发表于 2008-10-11 20:14:50

好也好不到哪里我想 64下也不会达到一次测试时钟能在10000内的

medie2005 · 发表于 2008-10-11 20:15:30

呵呵,我总觉得我的MultiModular()函数的效率太低,如果高度优化的话,还是能较大幅度的提高miller-rabin测试的速度. 另外,现在我做的工作都是在那个2,3表的基础上,这样,可能3与2的搭配不是很好也有可能,也就是说,可能存在其他素数与2搭配起来筛去的数更多.如果找到一个与2搭配起来比较好的素数c,那么,还是可能达到误判20次以内,甚至10次都有可能. 但是,要做上面的工作,前提是有一个10^16内的spsp(2)表,这个表中数据的总数肯定很大,也不利于找素数c.所以难度还是很大.

无心人 · 发表于 2008-10-11 20:21:41

http://oldweb.cecm.sfu.ca/pseudoprime/ 10^15内的伪素数似乎很多的样子

无心人 · 发表于 2008-10-11 20:21:59

http://oldweb.cecm.sfu.ca/pseudoprime/psp-search-slides.pdf

psp-search-slides.pdf (153.71 KB, 下载次数: 4)

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

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