找回密码
 欢迎注册
查看: 20860|回复: 15

[原创] 从左向右与从右向左的模幂算法的mathematica子函数

[复制链接]
发表于 2012-7-16 09:42:32 | 显示全部楼层 |阅读模式

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

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

×
  1. (*从左向右与从右向左的模幂算法的mathematica子函数*)
  2. (*底只能是正整数,而不能是矩阵!!!!!!!*)
  3. Clear["Global`*"];(*Clear all variables*)
  4. (*从左向右的模幂算法子函数*)
  5. PowerModLR[base0_,exponent0_,modulus0_]:=(*三个参量依次是:底\指数\模*)
  6.     Module[
  7.         {
  8.         base=Mod[base0,modulus0],
  9.         exponent=exponent0,
  10.         modulus=modulus0,
  11.         result,array,k (*局部变量*)
  12.         },
  13.         result=1;(*最终的求解的模幂的结果*)
  14.         array=IntegerDigits[exponent,2];(*把指数写成二进制的形式*)
  15.         Do[ result=Mod[result^2,modulus];
  16.             If[array[[k]]==1,result=Mod[result*base,modulus]],
  17.             {k,1,Length@array}
  18.         ];(*end of Do Loop*)
  19.         result
  20.     ]
  21. (*从右向左的模幂算法子函数*)
  22. PowerModRL[base0_,exponent0_,modulus0_]:=(*三个参量依次是:底\指数\模*)
  23.     Module[
  24.         {
  25.         base=base0,
  26.         exponent=exponent0,
  27.         modulus=modulus0,
  28.         result (*局部变量*)
  29.         },
  30.         result=1;(*最终的求解的模幂的结果*)
  31.         While[
  32.             exponent>0,
  33.             If[ Mod[exponent,2]==1,
  34.                 (*如果是奇数按照下列方式处理,以及处理指数*)
  35.                 result=Mod[result*base,modulus];exponent=exponent-1,
  36.                 (*如果是偶数,按照下列方式处理,以及处理指数*)
  37.                 base=Mod[base*base,modulus];exponent=exponent/2
  38.             ](*end of if*)
  39.         ];(*end of while*)
  40.         result
  41.     ]

  42. a=10^25+4;
  43. e=500!;
  44. n=142*29^2000+1;
  45. (*检验模幂算法子函数写的是否正确,与mathematica的PowerMod函数比较*)
  46. PowerModLR[a,e,n]-PowerMod[a,e,n]
  47. (*检验模幂算法子函数写的是否正确,与mathematica的PowerMod函数比较*)
  48. PowerModRL[a,e,n]-PowerMod[a,e,n]
  49. Print["从左向右的模幂函数的计算时间"]
  50. b=Timing@PowerModLR[a,e,n];b[[1]]
  51. Print["从右向左的模幂函数的计算时间"]
  52. b=Timing@PowerModRL[a,e,n];b[[1]]
  53. Print["mathematica本身的模幂函数计算时间"]
  54. b=Timing@PowerMod[a,e,n];b[[1]]
复制代码
计算结果如下:
Out[18]= 0

Out[19]= 0

During evaluation of In[13]:= 从左向右的模幂函数的计算时间

Out[21]= 0.5

During evaluation of In[13]:= 从右向左的模幂函数的计算时间

Out[23]= 0.703

During evaluation of In[13]:= mathematica本身的模幂函数计算时间

Out[25]= 0.469

不知道为什么从左向右的要比从右向左的更节省时间?????????
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-16 09:49:54 | 显示全部楼层
代码文件,不过请不要用mathematica打开,
我都是用vim打开,然后复制粘贴到mathematica的notebook中

code.nb

2.07 KB, 下载次数: 0, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-16 09:54:47 | 显示全部楼层
只能是整数为底,如果想要非指数为底,请自己改写函数!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-7-16 10:59:50 | 显示全部楼层
在做模幂算法时,将指数从左至右扫描,比从右至左扫描,可以减少临时变量的复制。
这是早有研究并有定论的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-16 12:22:55 | 显示全部楼层
在做模幂算法时,将指数从左至右扫描,比从右至左扫描,可以减少临时变量的复制。
这是早有研究并有定论的。
gxqcn 发表于 2012-7-16 10:59


看来还是你研究的比较多一些.
不过我是今天才知道的!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-16 14:09:53 | 显示全部楼层
  1. (*从左向右与从右向左的模幂算法的mathematica子函数*)
  2. (*地址:http://bbs.emath.ac.cn/thread-4462-1-1.html*)
  3. Clear["Global`*"];(*Clear all variables*)
  4. (*从右向左的模幂算法子函数*)
  5. PowerModRL[base0_,exponent0_,modulus0_]:=(*三个参量依次是:底\指数\模*)
  6.     Module[
  7.         {
  8.         base=base0,
  9.         exponent=exponent0,
  10.         modulus=modulus0,
  11.         result,array,k (*局部变量*)
  12.         },
  13.         result=1;(*最终的求解的模幂的结果*)
  14.         array=IntegerDigits[exponent,2];(*把指数写成二进制的形式*)
  15.         Do[ If[ array[[k]]==1,
  16.                 (*如果是奇数按照下列方式处理,以及处理指数*)
  17.                 result=Mod[result*base,modulus]
  18.             ];(*end of If*)
  19.             (*如果是偶数,按照下列方式处理,以及处理指数*)
  20.             base=Mod[base*base,modulus],
  21.             {k,Length@array,1,-1}
  22.         ];(*end of Do*)
  23.         result
  24.     ]
  25. (*从左向右的模幂算法子函数*)
  26. PowerModLR[base0_,exponent0_,modulus0_]:=(*三个参量依次是:底\指数\模*)
  27.     Module[
  28.         {
  29.         base=Mod[base0,modulus0],
  30.         exponent=exponent0,
  31.         modulus=modulus0,
  32.         result,array,k (*局部变量*)
  33.         },
  34.         result=1;(*最终的求解的模幂的结果*)
  35.         array=IntegerDigits[exponent,2];(*把指数写成二进制的形式*)
  36.         Do[ result=Mod[result^2,modulus];
  37.             If[array[[k]]==1,result=Mod[result*base,modulus]],
  38.             {k,1,Length@array}
  39.         ];(*end of Do Loop*)
  40.         result
  41.     ]

  42. a=10^25+4;
  43. e=500!;
  44. n=142*69^2000+1;
  45. (*检验模幂算法子函数写的是否正确,与mathematica的PowerMod函数比较*)
  46. PowerModLR[a,e,n]-PowerMod[a,e,n]
  47. (*检验模幂算法子函数写的是否正确,与mathematica的PowerMod函数比较*)
  48. PowerModRL[a,e,n]-PowerMod[a,e,n]
  49. Print["从左向右的模幂函数的计算时间"]
  50. b=Timing@PowerModLR[a,e,n];b[[1]]
  51. Print["从右向左的模幂函数的计算时间"]
  52. b=Timing@PowerModRL[a,e,n];b[[1]]
  53. Print["mathematica本身的模幂函数计算时间"]
  54. b=Timing@PowerMod[a,e,n];b[[1]]

复制代码
为了便于比较,我重新把两个方法的代码改写了一下,改成差不多的形式

从左向右的,只有一个result变量在不断被赋值,
而从右向左的,却有两个变量result与base在不断被赋值!
因此从左向右的比较节省时间!!!!!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-16 14:16:30 | 显示全部楼层
我从下面的地方知道从左向右的
http://www.google.com.hk/url?sa= ... WjvLEqf0oLrzC-_777w
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-16 14:17:05 | 显示全部楼层
论文的题目叫做
Modular Exponentiation using Parallel Multipliers
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-16 14:20:03 | 显示全部楼层
没想到从左向右与从右向左还是有很大差别的!!!!!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-16 14:23:28 | 显示全部楼层
Efficient modular exponentiation algorithms
http://eli.thegreenplace.net/200 ... tiation-algorithms/
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 12:43 , Processed in 0.048367 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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