跪求蒙哥玛利模幂算法的代码解释|蒙哥马利

最近在学习RSA算法的相关知识，对于其中的核心模密运算以及模密运算的核心——模乘也开始有一点点了解。

蒙哥马利模乘的优点在于减少了取模的次数（在大数的条件下）以及简化了除法的复杂度（在2的k次幂的进制下除法仅需要进行左移操作）。

一般的模密是调用模乘运算来实现的（正如你所列的代码），可以看一下下面一段文字（选自hellman2000的博客）：

模幂运算是RSA的核心算法，最直接地决定了RSA算法的性能。

针对快速模幂

运算这一课题，西方现代数学家提出了大量的解决方案，通常都是先将幂模运算转

化为乘模运算。

例如求D=C**15%N，由于：a*b%n=(a%n)*(b%n)%n，所以：

C1=C*C%N=C**2%N

C2=C1*C%N=C**3%N

C3=C2*C2%N=C**6%N

C4=C3*C%N=C**7%N

C5=C4*C4%N=C**14%N

C6=C5*C%N=C**15%N

即：对于E=15的幂模运算可分解为6个乘模运算，归纳分析以上方法可以发现

对于任意E，都可采用以下算法计算D=C**E%N：

D=1

WHILEE=0

IFE%2=0

C=C*C%N

E=E/2

ELSE

D=D*C%N

E=E-1

RETURND

继续分析会发现，要知道E何时能整除2，并不需要反复进行减一或除二的操

作，只需验证E的二进制各位是0还是1就可以了，从左至右或从右至左验证都可

以，从左至右会更简洁，设E=Sum[i=0ton](E*2**i)，0<=E<=1，则：

D=1

FORi=nTO0

D=D*D%N

IFE=1D=D*C%N

RETURND

这样，模幂运算就转化成了一系列的模乘运算。

其他一些关于大数运算、素数测试、模乘、模密运算，hellman2000的一篇文章有比较全面易懂的介绍，链接如下：http://bbs.sdu.edu.cn/pc/pccon.php?id=1308&nid=43763&pid=0&tag=0&tid=0