数学研发论坛

 找回密码
 欢迎注册

(*Miller-Rabin素性判定的mathematica子函数*)

已有 736 次阅读2017-5-5 10:13

(*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是返回结果*)
          ]


路过

雷人

握手

鲜花

鸡蛋

评论 (0 个评论)

facelist doodle 涂鸦板

您需要登录后才可以评论 登录 | 欢迎注册

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

GMT+8, 2020-10-30 01:22 , Processed in 0.031908 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

返回顶部