为什么梅森合数Mp的合数因子都是以2为基的强伪素数?
梅森合数Mp的定义:Mp=2^p-1为合数,并且p为素数。比如
2^29 - 1分解质因数得到
{{233, 1}, {1103, 1}, {2089, 1}}
排除M29,这个数有三个合数因子,我测试了一下,都通过了miller rabin测试,以2为基。
MR
MR
MR
结果都返回true
我从维基百科上看到这个结论,但是谁能证明一下呢?
Clear["Global`*"];(*Clear all variables*)
(*miller rabin子函数*)
MR:=Module[{s,m,t1,k},
s=0;m=n-1;While==0,m=m/2;s=s+1];
t1=PowerMod;
If];
k=0;While];
If,Return]
]
MR
MR
MR
对于M43的两个因子。
2^43 - 1=8796093022207={{431, 1}, {9719, 1}, {2099863, 1}}
MR
返回true 对M163进行测试,
结果也是如此
代码如下
(*选择大于1的合数因子*)
aaa=Select,And[#>1,Not@PrimeQ[#]]&]
(*对合数因子进行以2为基的miller rabin测试*)
bbb=MR[#,2]&/@aaa
(*统计测试结果*)
ccc=Tally
输出结果
{105826244207, 16563351642751, 77606621039153, 4158308781501239, \
19483514009133817, 3049454284123621481, 11663266256111186911, \
2928118869890693955479, 458293335998086701515047, \
2147306778162773425682441, 5444966325981078575081927, \
25512073120557082585375081, 3993011765633573362223747033, \
322712293769748729825537010567, 1002464733455002280154597767137, \
3834132933069162270508264798247, 600097759221772839888520270348471, \
2811723157900302652316835934504313, \
150657417396751927677594034629718319, \
705896569174407860595941718304957057, \
110483114904628180514196887638679762801, \
422565438231362784708740322088849687831, \
106087077691514234145382293018897081225359, \
16604175889671855364937107652554265512073887, \
77797900674357884219057394596540380453714961, \
11692013098647223345629478661730264157247460343807}
{True, True, True, True, True, True, True, True, True, True, True, \
True, True, True, True, True, True, True, True, True, True, True, \
True, True, True, True}
{{True, 26}}
本帖最后由 nyy 于 2022-10-25 14:02 编辑
证明:对于Mp=2^p-1来说,他的任何素数因子q,都有q=2*k*p+1
而Mp=2^p-1=0(mod q)
q1=1(mod p)
q2=1(mod p)
所以q1*q2=1(mod p)
剩下的见三楼吧
https://bbs.emath.ac.cn/thread-18615-1-1.html
https://bbs.emath.ac.cn/forum.php?mod=redirect&goto=findpost&ptid=18615&pid=93239&fromuid=14149
页:
[1]