数学研发论坛

 找回密码
 欢迎注册
查看: 14335|回复: 23

[原创] (*Miller-Rabin素性判定的mathematica子函数*)

[复制链接]
发表于 2012-7-5 13:46:25 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
  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.           ]
复制代码

评分

参与人数 1鲜花 +1 收起 理由
gxqcn + 1 已应6#要求编辑修改

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-5 13:48:02 | 显示全部楼层
/viewthread.php?tid=950&highlight=
原帖在这,但是这个不是子函数的形式存在的,所以用起来不好用,
还是这个用子函数存在的比较好用一些!!!!!!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-5 13:51:42 | 显示全部楼层
被管理员清空性删除
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-5 13:55:30 | 显示全部楼层
如果子函数的返回结果是1,则可能是素数,
如果子函数的返回结果是0,则一定是合数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-5 13:58:17 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-6 09:50:11 | 显示全部楼层
  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.
重新贴上正确的!!!!!!!!!!!!!!!!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-6 09:54:42 | 显示全部楼层
多么好的代码呀!!!!!!!!!!!!!!!!!!
赞美我自己一下!!!!!!!!!!!!!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-6 09:54:59 | 显示全部楼层
忍不住再赞美自己一下!!!!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-6 09:56:50 | 显示全部楼层
管理员把这个帖子的1楼和3楼的内容删除了吧,
因为那的帖子的代码有bug.
是只删除内容,不删除主题的删除!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-6 09:58:12 | 显示全部楼层
提示一下,先删除3楼的内容,再删除1楼的内容,
如果先删除1楼的,那么3楼可能变成2楼,
然后错误地把4楼的删除了!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-9-26 15:22 , Processed in 0.059281 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表