数学研发论坛

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

[讨论] 郭有没有兴趣做出一个确定性的素性检测函数

[复制链接]
发表于 2010-7-8 15:40:24 | 显示全部楼层
好多都错了,考虑不周啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-8 15:42:12 | 显示全部楼层
对于搜索连续长度为10以上的素数,我们只需要搜索形式如2*3*5*11*k-1的素数。
而如果搜索长度为12以上的,只需要搜索形式如2*3*5*11*13*k-1的素数
mathe 发表于 2010-7-8 15:29


Why?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 15:43:11 | 显示全部楼层
是必需形式么?
是的话,我修改程序去
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-8 15:45:52 | 显示全部楼层
是必须形式。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 15:46:30 | 显示全部楼层
那8,9,11,13都要什么形式?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-8 15:50:38 | 显示全部楼层
由于
$p_{n+1}=2p_n+1$
我们可以有
$p_{n+1}-p_n=2(p_n-p_{n-1})=...=2^n(p_1-p_0)$
于是$p_n=(2^n-1)(p_1-p_0)+p_0=(2^n-1)(p_0+1)+p_0=2^n(p_0+1)-1$
如果2是素数P的原根,那么我们知道,上面序列长度最大P-2,(除非第一个数据是P),这个是因为如果长度达到P-1
那么$2^0(p_0+1),2^1(p_0+1),...,2^{P-2}(p_0+1)$可以构成P的一个完系,其中必然有一个为1,所以对应的$p_i$是P的倍数。
由于2是素数3,5,11,13的原根,我们可以有前面的结论

评分

参与人数 1威望 +3 贡献 +3 收起 理由
gxqcn + 3 + 3 观点精辟

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-8 15:53:51 | 显示全部楼层
而再后面几个以2为原根的素数为19,29,37.
当然,我们也可以用素数7在此过滤,比如我们计算可知这些素数模7的余数必须是{2,4,5,6}之一,不过这个过滤效果就要差很多了,使用起来没有那么方便
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 15:57:14 | 显示全部楼层


你的结论对计算最小长度为8的可以么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-8 16:02:55 | 显示全部楼层
那只可以用2*3*5*k-1(当然可以添加对关于模7和11的一些特殊处理,但是效果没有那么好了,实际11比7还有效一些)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-8 16:04:43 | 显示全部楼层
Pari/Gp通过冗长的计算找出一个10个素数的链了:
26089808579
52179617159
104359234319
208718468639
417436937279
834873874559
1669747749119
3339495498239
6678990996479
13357981992959
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2020-10-27 12:02 , Processed in 0.073392 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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