能找到以2, 5, 26, 677为底的强伪素数吗?
tb=NestList[(#^2+1)&,2,7]tb=NestList[(#^2+1)&,2,7]
{2, 5, 26, 677, 458330, 210066388901, 44127887745906175987802, 1947270476915296449559703445493848930452791205}
谁能找一个给我看看?
我知道肯定有,但是我自己找不到,谁能帮我找几个?
下面是Miller rabin的mathematica子函数代码
MRTest:=(*n0被判定的正奇整数,a0选用的底*)
Module[{n=n0,
a=a0,
m,s,t1,k,t2,out=0(*局部变量*)
},
(*先写成n=m*2^s+1的形式,n和m是奇数*)
m=n-1;
s=0;
While==0,m=m/2;s=s+1];
(*继续判定*)
(*先检查a^m Mod n是否等于1*)
t1=PowerMod;
If[ t1==1, (*判定a^m Mod n是否等于1*)
out=1,
(*如果a^m Mod n不等于1,再不断平方a^m Mod n,
看结果是否等于-1,也就是n-1*)
k=0;
t2=t1;
While];
(*如果可能是符合-1,则返回1,如果不是-1则返回0*)
If
]
out(*out是返回结果*)
]
808460124355439022735025127668137421
是以2, 5, 26为底的强伪素数,
但是不是677为底的强伪素数 82824364075160891096445017152530181
是以
2, 5, 26, 677, 458330为底的强伪素数
我的想法就是
对于任意给定的奇数N
取集合
M={2, 5, 26, 677, 458330, 210066388901, 44127887745906175987802, 1947270476915296449559703445493848930452791205.....}
中小于N的数为底,
然后进行Miller rabin测试,
如果都说是素数,那么就是素数 如果我们找到素数$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的平方剩余
然后比如让计算搜索p=13*20*677*h+1,p和2p-1都是素数，马上可以找出
p=11617321,q=23234641,pq=269924282816761符合条件
当然如果你需要通过更多的数的测试，需要让p满足更多条件 比如
p=2654857922531631550908127777783100805691784217383544766667103654601260254587952647942139401
q=2p-1=5309715845063263101816255555566201611383568434767089533334207309202520509175905295884278801
pq=14096541177657941106619621511984845600914597981448329842509459629778768974299630789490799037049831061404463075160907606925950664792346493779202263728811248037757799831078441891138201
应该符合你所有的条件。 62981647709912821
249363882001089901 mathe 发表于 2017-6-6 14:38
62981647709912821
249363882001089901
我只想给你点一万个赞! 对于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$
页:
[1]