数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【数学研究】 › 数学软件 › (*Miller-Rabin素性判定的mathematica子函数*)
123下一页
返回列表 发新帖
查看: 30961|回复: 23

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

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

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

您需要 登录 才可以下载或查看，没有账号？欢迎注册

×
  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#要求编辑修改

查看全部评分

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复

使用道具 举报

mathematica
 楼主| 发表于 2012-7-5 13:48:02 | 显示全部楼层
http://bbs.emath.ac.cn/viewthread.php?tid=950&highlight=
原帖在这,但是这个不是子函数的形式存在的,所以用起来不好用,
还是这个用子函数存在的比较好用一些!!!!!!!!!
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathematica
 楼主| 发表于 2012-7-5 13:51:42 | 显示全部楼层
被管理员清空性删除
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathematica
 楼主| 发表于 2012-7-5 13:55:30 | 显示全部楼层
如果子函数的返回结果是1,则可能是素数,
如果子函数的返回结果是0,则一定是合数
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathematica
 楼主| 发表于 2012-7-5 13:58:17 | 显示全部楼层
http://hi.baidu.com/白浪
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathematica
 楼主| 发表于 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.
重新贴上正确的!!!!!!!!!!!!!!!!!!!
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathematica
 楼主| 发表于 2012-7-6 09:54:42 | 显示全部楼层
多么好的代码呀!!!!!!!!!!!!!!!!!!
赞美我自己一下!!!!!!!!!!!!!!!!
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathematica
 楼主| 发表于 2012-7-6 09:54:59 | 显示全部楼层
忍不住再赞美自己一下!!!!!!!
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathematica
 楼主| 发表于 2012-7-6 09:56:50 | 显示全部楼层
管理员把这个帖子的1楼和3楼的内容删除了吧,
因为那的帖子的代码有bug.
是只删除内容,不删除主题的删除!
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathematica
 楼主| 发表于 2012-7-6 09:58:12 | 显示全部楼层
提示一下,先删除3楼的内容,再删除1楼的内容,
如果先删除1楼的,那么3楼可能变成2楼,
然后错误地把4楼的删除了!
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

123下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-5-19 14:12 , Processed in 0.047501 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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