找回密码
 欢迎注册
查看: 18290|回复: 18

[原创] 能找到以2, 5, 26, 677为底的强伪素数吗?

[复制链接]
发表于 2017-6-5 13:31:11 | 显示全部楼层 |阅读模式

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

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

×
tb=NestList[(#^2+1)&,2,7]
  1. tb=NestList[(#^2+1)&,2,7]
复制代码


{2, 5, 26, 677, 458330, 210066388901, 44127887745906175987802, 1947270476915296449559703445493848930452791205}
谁能找一个给我看看?
我知道肯定有,但是我自己找不到,谁能帮我找几个?
下面是Miller rabin的mathematica子函数代码
  1. MRTest[n0_,a0_]:=(*n0被判定的正奇整数,a0选用的底*)
  2.     Module[{n=n0,
  3.             a=a0,
  4.             m,s,t1,k,t2,out=0(*局部变量*)
  5.            },
  6.             (*先写成n=m*2^s+1的形式,n和m是奇数*)
  7.             m=n-1;
  8.             s=0;
  9.             While[Mod[m,2]==0,m=m/2;s=s+1];
  10.             (*继续判定*)
  11.             (*先检查a^m Mod n是否等于1*)
  12.             t1=PowerMod[a,m,n];
  13.             If[ t1==1,    (*判定a^m Mod n是否等于1*)
  14.                 out=1,
  15.                 (*如果a^m Mod n不等于1,再不断平方a^m Mod n,
  16.                   看结果是否等于-1,也就是n-1*)
  17.                 k=0;
  18.                 t2=t1;
  19.                 While[k<s-1&&t2!=n-1,k=k+1;t2=Mod[t2*t2,n]];
  20.                 (*如果可能是符合-1,则返回1,如果不是-1则返回0*)
  21.                 If[t2==n-1,out=1,out=0]
  22.               ]
  23.             out(*out是返回结果*)
  24.           ]
复制代码

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-6-5 13:47:11 | 显示全部楼层
808460124355439022735025127668137421
是以2, 5, 26为底的强伪素数,
但是不是677为底的强伪素数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-6-5 13:49:49 | 显示全部楼层
82824364075160891096445017152530181
是以
2, 5, 26, 677, 458330为底的强伪素数

点评

1836067393621  发表于 2017-6-6 14:09
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-6-5 14:03:29 | 显示全部楼层
我的想法就是
对于任意给定的奇数N
取集合
M={2, 5, 26, 677, 458330, 210066388901, 44127887745906175987802, 1947270476915296449559703445493848930452791205.....}
中小于N的数为底,
然后进行Miller rabin测试,
如果都说是素数,那么就是素数

点评

1836067393621mathe破了这个想法!  发表于 2017-6-6 17:17
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-5 14:55:52 | 显示全部楼层
如果我们找到素数$p$,而且$q=2p-1$也是素数,而且上面需要测试的元素a都是q的平方剩余,
于是$a^{p-1} -= 1(mod p)$,而且$a^{{q-1}/2} = a^{p-1} -= 1(mod q)$
于是$a^{pq-1}=a^{(p-1)q+q-1}=1(mod pq)$
于是pq是关于a的强伪素数。
于是我们只要随机找出素数p,2p-1使得2, 5, 26, 677都是2p-1的平方剩余即可。
于是要求p除20余数为1,而且2p-1是13和677的平方剩余
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-5 15:04:25 | 显示全部楼层
然后比如让计算搜索p=13*20*677*h+1,p和2p-1都是素数,马上可以找出
p=11617321,q=23234641,pq=269924282816761符合条件
当然如果你需要通过更多的数的测试,需要让p满足更多条件
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-5 15:16:33 | 显示全部楼层
比如
p=2654857922531631550908127777783100805691784217383544766667103654601260254587952647942139401
q=2p-1=5309715845063263101816255555566201611383568434767089533334207309202520509175905295884278801
pq=14096541177657941106619621511984845600914597981448329842509459629778768974299630789490799037049831061404463075160907606925950664792346493779202263728811248037757799831078441891138201
应该符合你所有的条件。

点评

也就是说每个待测试元素关于p,q的最小次数中2的幂需要时相等的,实际上对于随机挑选的p,q这个概率是挺大的,然后我们需要产生多组数据,然后寻找其中2的幂都相等的结果即可  发表于 2017-6-5 16:30
知道了,我做的是费马测试,你要求的是Miller-Rabin测试  发表于 2017-6-5 16:21
{0, 0, 0, 0, 1, 0, 1, 0, 0},0表示没通过测试,1表示通过了测试  发表于 2017-6-5 16:19
你可以使用上面我给的子函数代码自己验证一下  发表于 2017-6-5 16:18
经验证,不是2,5为底的强伪素数  发表于 2017-6-5 16:18
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-6 14:38:42 | 显示全部楼层
62981647709912821
249363882001089901

点评

671122899379341181 1061660257875362701 4265264694305560501  发表于 2017-6-6 14:41

评分

参与人数 1威望 +5 金币 +5 贡献 +5 经验 +5 鲜花 +5 收起 理由
mathematica + 5 + 5 + 5 + 5 + 5 给你点一万个赞!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-6-6 17:19:32 | 显示全部楼层
mathe 发表于 2017-6-6 14:38
62981647709912821
249363882001089901

我只想给你点一万个赞!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-7 09:27:02 | 显示全部楼层
对于a=2,我们可以得出$2p-1 -= +-1(mod 8)$
所以必然$p-=1(mod 4),2p-1 -= 1(mod 8)$
由此我们可以得出$1=((a),(2p-1))=((2p-1),(a))$
于是对于a=5有$2p-1 -= +-1(mod 5)$
排除$p=5$,那么只能$p-=1(mod 5)$
由此我们只需要搜索$p-=1(mod 20)$的情况
然后后面的搜索,就需要依次对每个a,设$p-1=2^h*s$,其中s是奇数
然后一次计算$u_0=Mod(a,p)^s,v_0=Mod(a,q)^s$
如果$u_0,v_0$之1是$+-1$但是不相等,那么搜索失败
不然继续计算$u_1=Mod(u_0,p)^2,v_1=Mod(v_1,p)^2$
等等,知道双方都达到1或出现不同时为$+-1$

点评

你的LaTeX真牛逼,比我牛逼多了,我只会用mathematica软件搞,或者mathtype搞  发表于 2017-6-7 13:22
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 19:33 , Processed in 0.048092 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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