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

mathematica

1. (*Miller-Rabin素性判定的mathematica子函数*)
2. Clear["Global`*"];(*Clear all variables*)
3. MRTest[n0_,a0_]:=(*n0被判定的正奇整数,a0选用的底*)
4. Module[{n=n0,
5. a=a0,
6. m,s,t1,k,t2,out=0(*局部变量*)
7. },
8. (*先写成n=m*2^s+1的形式,n和m是奇数*)
9. m=n-1;
10. s=0;
11. While[Mod[m,2]==0,m=m/2;s=s+1];
12. (*继续判定*)
13. (*先检查a^m Mod n是否等于1*)
14. t1=PowerMod[a,m,n];
15. If[ t1==1, (*判定a^m Mod n是否等于1*)
16. out=1,
17. (*如果a^m Mod n不等于1,再不断平方a^m Mod n,
18. 看结果是否等于-1,也就是n-1*)
19. k=0;
20. t2=t1;
21. While[k<s-1&&t2!=n-1,k=k+1;t2=Mod[t2*t2,n]];
22. (*如果可能是符合-1,则返回1,如果不是-1则返回0*)
23. If[t2==n-1,out=1,out=0]
24. ]
25. out(*out是返回结果*)
26. ]

复制代码

mathematica

http://bbs.emath.ac.cn/viewthread.php?tid=950&highlight= 原帖在这,但是这个不是子函数的形式存在的,所以用起来不好用, 还是这个用子函数存在的比较好用一些!!!!!!!!!

mathematica

被管理员清空性删除

mathematica

如果子函数的返回结果是1,则可能是素数, 如果子函数的返回结果是0,则一定是合数

mathematica

http://hi.baidu.com/白浪

mathematica

1. (*Miller-Rabin素性判定的mathematica子函数*)
2. Clear["Global`*"];(*Clear all variables*)
3. MRTest[n0_,a0_]:=(*n0被判定的正奇整数,a0选用的底*)
4. Module[{n=n0,
5. a=a0,
6. m,s,t1,k,t2,out=0(*局部变量*)
7. },
8. (*先写成n=m*2^s+1的形式,n和m是奇数*)
9. m=n-1;
10. s=0;
11. While[Mod[m,2]==0,m=m/2;s=s+1];
12. (*继续判定*)
13. (*先检查a^m Mod n是否等于1*)
14. t1=PowerMod[a,m,n];
15. If[ t1==1, (*判定a^m Mod n是否等于1*)
16. out=1,
17. (*如果a^m Mod n不等于1,再不断平方a^m Mod n,
18. 看结果是否等于-1,也就是n-1*)
19. k=0;
20. t2=t1;
21. While[k<s-1&&t2!=n-1,k=k+1;t2=Mod[t2*t2,n]];
22. (*如果可能是符合-1,则返回1,如果不是-1则返回0*)
23. If[t2==n-1,out=1,out=0]
24. ]
25. out(*out是返回结果*)
26. ]

复制代码

这个代码是正确的,上面的两个代码都有bug,不过原代码没有bug, 结果被我修正一下出现了bug. 重新贴上正确的!!!!!!!!!!!!!!!!!!!

mathematica

多么好的代码呀!!!!!!!!!!!!!!!!!! 赞美我自己一下!!!!!!!!!!!!!!!!

mathematica

忍不住再赞美自己一下!!!!!!!

mathematica

管理员把这个帖子的1楼和3楼的内容删除了吧, 因为那的帖子的代码有bug. 是只删除内容,不删除主题的删除!

mathematica

提示一下,先删除3楼的内容,再删除1楼的内容, 如果先删除1楼的,那么3楼可能变成2楼, 然后错误地把4楼的删除了!