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

数学研发论坛

 找回密码
 欢迎注册

QQ登录

只需一步,快速开始

查看: 39346|回复: 219

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

[复制链接]
发表于 2008-10-4 09:03:20 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
精华
看 卡米切尔数 的那个问题有人重新关注了
出个更困难的问题
<<<<<<<<<<<<<<<<****>>>>>>>>>>>>>>
| 素性检验需要以若干素数为底做米勒-罗宾测试
| 2,3,5,7是经常使用的素数底
|                                                                                      
| 现在考虑下面的问题                        
| 能否以比较快的速度求出                    
| 10^32内的能同时通过2,3,5,7测试的合数
-*-@@-*-@@-*-@@-%%%-@@-*-@@-*-@@-*-
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-4 23:39:23 | 显示全部楼层
是这个意思吗?
a^1 mod 2=1
a^2 mod 3=1
a^4 mod 5=1
a^6 mod 7=1
a<10^32
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-5 11:56:49 | 显示全部楼层

回复 1# 无心人 的帖子

$10^32=10^20 KG$, 假如一块1000G的硬盘占用0.2升,那么这些硬盘占用的空间恐怕超过5亿立方公里,你有那么多硬盘来存储结果吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-5 15:47:54 | 显示全部楼层
我也觉得我说的范围有点大
但没有你说的那么恐怖吧

据我知道10^16内满足这个条件的不会很多
是以10^8做单位的

=============================
所以这个题目改成10^16内的数字
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-5 19:32:02 | 显示全部楼层
呵呵
不是通过麦森测试
那个太多了

谢谢media2005提供的数据
我想得到具体的求解方法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-5 19:57:57 | 显示全部楼层
呵呵,还漏掉了一个46,856,248,255,981。

http://www.bell-labs.com/user/bleichen/diss/thesis.html中,可以得到一个10^16以内,通过2,3为底的米勒-罗宾测试的合数表.
我们只需要对表中的每个数再判断是否能通过以5,7 为底的米勒-罗宾测试就ok了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-5 20:54:23 | 显示全部楼层
THX
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-6 11:03:31 | 显示全部楼层
抱歉,我理解错题意了,我以为是可以被2,3,5,7之一整除呢。实际上应该是同时不可被2,3,5,7整除。这样的话,范围就小多了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-6 13:49:12 | 显示全部楼层


我想知道那些简单的素性测试程序的参数时如何挑选出来的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-6 14:59:10 | 显示全部楼层
see this: http://math.crg4.com/primes.html
在“My Efficient Sets of Bases”一段中,提到了:
“For these calculations, I used lists of pseudoprimes from Richard Pinch (2-pseudoprimes up to 10^13), William Galway (2-pseudoprimes up to 10^15), and Daniel Bleichenbacher (2- and 3-strong pseudoprimes up to 10^16). My actual calculations were carried out in C#, C++, and PARI/GP.”
因此,还是用类似我上面的方法来做的。
如果有兴趣,也可以自己改进五元组测试基。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2017-3-31 04:31 , Processed in 0.237770 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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