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

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

[复制链接]
发表于 2010-7-8 18:06:06 | 显示全部楼层
由于
$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 ...
mathe 发表于 2010-7-8 15:50

利用$p_n=2^n(p_0+1)-1$,假设查找长度为L的序列
我们可以直接设计对应的筛法。
首先,对于特别的小素数,我们直接求解出允许的余数,特别是余数只能是-1的数字可以特殊处理。
而对于余下的数,那么对于任何素数P,如果$p_n!=P$,那么我们知道
$2^n(p_0+1)-1!=0(mod P)$,即$p_0!=2^-n-1(mod P)$,我们只要计算出2关于P的数论倒数h,然后筛除$h^0-1,h^1-1,...,h^{L-1}-1 (mod P)$
可以通过这种方法将大量较小的P(比如不超过10000)全部进行筛选,那么余下的候选数将会很少。然后可以再次逐一判断
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-9 07:55:01 | 显示全部楼层
$(2^10t-1)(Mod P)$未必是$2^10t-1$
mathe 发表于 2010-7-8 17:13


这句话没看明白。

我还是比较坚持昨天的“加强”说法(并且将先前2的指数加1,已在原帖修改)。

以“搜索连续长度为10以上的素数”来说,已有结论我们“需要搜索形式如2*3*5*11*k-1的素数”。
再加上 $p_n=2^n(p_0+1)-1$(注意: 我没把 $p_0$ 它作为素数序列中的一员,而是其前一个,但为整数),
即 $(2*3*5*11)|(p_10+1)$ 且 $2^10|(p_10+1)$,
所以 $(2^10*3*5*11)|(p_10+1)$
这样顺理成章即可得到加强版:“我们只需要搜索形式如2^10*3*5*11*k-1的素数”


实际上,上述结论用来检验 40# 得到的数据“13357981992959”也是成立的:

$13357981992959 = 2^11*3^2*5*11*19*61*11369 - 1$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-9 09:41:46 | 显示全部楼层
怎样理解应该是对的。也就是说测试$p_n$而不是$p_0$.
不过搜索空间是一样的,只是素数检测先判断$p_n$而不是$p_0$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-10 16:52:12 | 显示全部楼层
26# 无心人


10^6内少了一组数据
[89,179,359,719,1439,2879]
10^6内其他三组6项的
[127139,254279,508559,1017119,2034239,4068479]
[405269,810539,1621079,3242159,6484319,12968639]
[810809,1621619,3243239,6486479,12972959,25945919]
漏掉的一组:63419 ,126839, 253679, 507359 ,1014719, 2029439

长度为7的一组里有一个不是素数
[164229,4328459,8656919,17313839,34627679,69255359,138510719]中的值
164229=3×13×4211
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-10 17:24:53 | 显示全部楼层
11链的
665043081119,1330086162239,2660172324479,5320344648959,10640689297919,21281378595839,42562757191679,85125514383359,170251028766719,340502057533439,681004115066879
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-10 17:38:57 | 显示全部楼层
12链
554688278429,1109376556859,2218753113719,4437506227439,8875012454879,17750024909759,35500049819519,71000099639039,142000199278079,284000398556159,568000797112319,1136001594224639
13链
4090932431513069,8181864863026139,16363729726052279,32727459452104559,65454918904209119,130909837808418239,261819675616836479,523639351233672959,1047278702467345919,2094557404934691839,4189114809869383679,8378229619738767359,16756459239477534719
14链
95405042230542329,190810084461084659,381620168922169319,763240337844338639,1526480675688677279,3052961351377354559,6105922702754709119,12211845405509418239,24423690811018836479,48847381622037672959,97694763244075345919,195389526488150691839,390779052976301383679,781558105952602767359
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-10 18:14:20 | 显示全部楼层
用的什么算法?这么大的范围应该是需要事先筛选一些较多的素数模了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-10 20:16:09 | 显示全部楼层
64#不好意思,是我复制少了个数字2
应该是
[2164229,4328459,8656919,17313839,34627679,69255359,138510719]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-10 20:25:32 | 显示全部楼层
第二组6个的我也忘记为什么漏掉了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-10 20:29:17 | 显示全部楼层
最小的5, 6, 7链已经找到
后面的大家努力
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-11-21 20:33 , Processed in 0.036954 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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