(*Miller-Rabin素性判定的mathematica子函数*)
Clear["Global`*"];(*Clear all variables*)
MRTest[n0_,a0_]:=(*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[Mod[m,2]==0,m=m/2;s=s+1];
(*继续判定*)
(*先检查a^m Mod n是否等于1*)
t1=PowerMod[a,m,n];
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[k<s-1&&t2!=n-1,k=k+1;t2=Mod[t2*t2,n]];
(*如果可能是符合-1,则返回1,如果不是-1则返回0*)
If[t2==n-1,out=1,out=0]
]
out(*out是返回结果*)
]
