数学研发网设为首页收藏本站

数学研发论坛

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

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

[复制链接]
 楼主| 发表于 2010-6-11 08:57:29 | 显示全部楼层
试除法也有一点点弊端,要占用点内存空间
不知道诸位谁有兴趣,把打包的65536内的素数表
和解包算法发出来

要求是打包的越短越好,解包也要速度快才好
由于解包是顺序解包,也不限定一些高压缩方案
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-6-11 09:35:52 | 显示全部楼层
这个就是以前gxqcn提过的分组方法啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-14 11:34:25 | 显示全部楼层
呃,很多东西都忘记了,重新看了一遍
因为我想写个素性测试程序

现在我有想做10^16的spsp(2)的想法了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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次比较,也比一次测试时间少
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-3-2 03:44:43 | 显示全部楼层
2*3*5*7 = 210

a * 210 +r:
r = 1;
r = 11;
r = 13;
r = 17;
r = 19;
……
……
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2017-5-25 16:38 , Processed in 0.379371 second(s), 21 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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