找回密码
 欢迎注册
楼主: 无心人

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

[复制链接]
发表于 2008-10-11 19:10:33 | 显示全部楼层
对测试基(2,3,13,p,q),已经对p,q在10^5内的素数值进行了穷举,得到的结果是:
很遗憾,在10^16范围内,竟然没有一组误判次数在40次以下!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-11 19:15:08 | 显示全部楼层
看规律基本上那组(2,3,5,4057,696811)最好了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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万次就算不错了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-11 20:08:24 | 显示全部楼层
64位二进制数字进行Miller-Rabin测试,
若在64位OS下肯定比在32位系统下好。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-11 20:14:50 | 显示全部楼层


好也好不到哪里
我想
64下也不会达到一次测试时钟
能在10000内的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 09:16 , Processed in 0.048850 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表