求证梅森合数与费马合数都通过了以2为底的miller rabin测试！
梅森合数=当p为素数的时候，2^p-1也是合数的情况（排除梅森素数），梅森数是素数肯定能通过以2为底的miller rabin测试！费马合数=就是费马数为合数的情况，费马数是素数肯定能通过以2为底的miller rabin测试！
请证明这两种情况都能通过以2为底的miller rabin测试！ 先看费马合数的问题：
Clear["Global`*"];
n=2^(2^7)+1;
Do[ a=PowerMod;
If;
Print[{k,a}];
If,Break[]],
{k,0,200}]
求解结果
{0,2}
{1,4}
{2,16}
{3,256}
{4,65536}
{5,4294967296}
{6,18446744073709551616}
{7,-1}
简单起见：
n=2^(2^7)+1=2^128+1
n-1=2^128=2^121*2^7
2^(2^7)=-1(mod n)
所以费马合数肯定能通过这个测试了
其余同理费马合数都可以证明 梅森合数的情况
简单起见
n=2^67-1
n-1=2^67-1-1=2*(2^66-1)
根据费马小定理
(2^66-1)=0 (mod 67)
假设2^66-1=t*67(很显然t是一个奇数)
所以2^(2^66-1)=2^(t*67)=(2^67)^t=1^t=1 (mod n)
所以肯定通过了这个测试，以此类推！ 我以为这会是个难题，没想到我自己好好想还是能想出来的！
页:
[1]