从左向右与从右向左的模幂算法的mathematica子函数

mathematica

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. ]
43. a=10^25+4;
44. e=500!;
45. n=142*29^2000+1;
46. (*检验模幂算法子函数写的是否正确,与mathematica的PowerMod函数比较*)
47. PowerModLR[a,e,n]-PowerMod[a,e,n]
48. (*检验模幂算法子函数写的是否正确,与mathematica的PowerMod函数比较*)
49. PowerModRL[a,e,n]-PowerMod[a,e,n]
50. Print["从左向右的模幂函数的计算时间"]
51. b=Timing@PowerModLR[a,e,n];b[[1]]
52. Print["从右向左的模幂函数的计算时间"]
53. b=Timing@PowerModRL[a,e,n];b[[1]]
54. Print["mathematica本身的模幂函数计算时间"]
55. 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 不知道为什么从左向右的要比从右向左的更节省时间?????????

mathematica

代码文件,不过请不要用mathematica打开, 我都是用vim打开,然后复制粘贴到mathematica的notebook中

mathematica

只能是整数为底,如果想要非指数为底,请自己改写函数!

gxqcn

在做模幂算法时，将指数从左至右扫描，比从右至左扫描，可以减少临时变量的复制。 这是早有研究并有定论的。

mathematica

在做模幂算法时，将指数从左至右扫描，比从右至左扫描，可以减少临时变量的复制。 这是早有研究并有定论的。 gxqcn 发表于 2012-7-16 10:59

看来还是你研究的比较多一些. 不过我是今天才知道的!

mathematica

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

复制代码

为了便于比较,我重新把两个方法的代码改写了一下,改成差不多的形式 从左向右的,只有一个result变量在不断被赋值, 而从右向左的,却有两个变量result与base在不断被赋值! 因此从左向右的比较节省时间!!!!!!!!

mathematica

我从下面的地方知道从左向右的 http://www.google.com.hk/url?sa= ... WjvLEqf0oLrzC-_777w

mathematica

论文的题目叫做 Modular Exponentiation using Parallel Multipliers

mathematica

没想到从左向右与从右向左还是有很大差别的!!!!!!!!

mathematica

Efficient modular exponentiation algorithms http://eli.thegreenplace.net/200 ... tiation-algorithms/