蒙哥马利算法（见过的资料中讲的最透彻的）

转载自：https://blog.csdn.net/zgzczzw/article/details/52712980

这篇文章为大家梳理一下整个蒙哥马利算法的本质，蒙哥马利算法并不是一个独立的算法，而是三个相互独立又相互联系的算法集合，其中包括

其中蒙哥马利幂乘是RSA加密算法的核心部分。

梳理几个概念，试想一个集合是整数模N之后得到的 ZN={0,1,2,⋯,N−1}ZN={0,1,2,⋯,N−1}

注：N在base-b进制下有lNlN位。 比如10进制和100进制，都属于base-10进制，因为100=102100=102，所以b=10。在10进制下，667的lN=3lN=3

这样的集合叫做N的剩余类环，任何属于这个集合Z的x满足以下两个条件： 1. 正整数 2. 最大长度是lNlN

这篇文章中讲到的蒙哥马利算法就是用来计算基于ZNZN集合上的运算，简单讲一下原因，因为RSA是基于大数运算的，通常是1024bit或2018bit，而我们的计算机不可能存储完整的大数，因为占空间太大，而且也没必要。因此，这种基于大数运算的加密体系在计算的时候都是基于ZNZN集合的，自然，蒙哥马利算法也是基于ZNZN。

在剩余类环上，有两种重要的运算，一类是简单运算，也就是加法和减法，另一类复杂运算，也就是乘法。我们比较熟悉的是自然数集上的运算，下面看下怎么从自然数集的运算演变成剩余类环上的运算。

对于加法运算，如果计算x±y (mod N)x±y (mod N) (0⩽x,yN的最小的k是3，所以ρ=bk=103=1000ρ=bk=103=1000 ω=−N−1 (mod ρ)=−667−1 (mod ρ)=997ω=−N−1 (mod ρ)=−667−1 (mod ρ)=997

因为x=421x=421，所以x^=x⋅ρ(mod N)=421⋅1000(mod 667)=123x^=x⋅ρ(mod N)=421⋅1000(mod 667)=123 因为y=422y=422，所以y^=y⋅ρ(mod N)=422⋅1000(mod 667)=456y^=y⋅ρ(mod N)=422⋅1000(mod 667)=456

所以计算x^x^和y^y^蒙哥马利乘结果是

x^⋅y^⋅ρ−1=(421⋅1000⋅422⋅1000)⋅1000−1 (mod 667)x^⋅y^⋅ρ−1=(421⋅1000⋅422⋅1000)⋅1000−1 (mod 667) (421⋅422)⋅1000 (mod 667)(421⋅422)⋅1000 (mod 667) (240)⋅1000 (mod 667)(240)⋅1000 (mod 667) 547 (mod 667)547 (mod 667)

然后总结一下蒙哥马利约减和蒙哥马利乘法的伪代码实现，这个算法其实就是从蒙哥马利预备知识讲到的算法演变来的。

上面的例子用这个算法可以描述为

蒙哥马利算法是一套很完美的算法，为什么这么说呢，你看一开始已知xx，我们要求x^=x⋅ρx^=x⋅ρ，这个过程可以通过蒙哥马利乘法本身来计算，输入参数xx和ρ2ρ2，计算结果就是x^=x⋅ρx^=x⋅ρ。然后在最后，我们知道x^=x⋅ρx^=x⋅ρ，要求得xx的时候，同样可以通过蒙哥马利算法本身计算，输入参数x^x^和11，计算结果就是xx。有没有一种因就是果，果就是因的感觉，这就是为什么说蒙哥马利算法是一套很完美的算法。

最后，才说到我们最开始提到的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 WHILE E>0 IF E%2=0 C=C*C % N E=E/2 ELSE D=D*C % N E=E-1 RETURN D 继续分析会发现，要知道E 何时能整除 2，并不需要反复进行减一或除二的操作，只需验证E 的二进制各位是0 还是1 就可以了，从左至右或从右至左验证都可以，从左至右会更简洁， 设E=Sum[i=0 to n](E*2**i)，0N，我们还知道NN在bb进制下是lNlN位，所以当k=lNk=lN的时候肯定是符合要求。

b=2ωb=2ω 所以ρ=bk=(2ω)kρ=bk=(2ω)k

ρ2=(2w)k)2=22⋅k⋅ω=22⋅lN⋅ωρ2=(2w)k)2=22⋅k⋅ω=22⋅lN⋅ω，算法如下

至此整个蒙哥马利算法就全部说完了。通过这个算法，我们可以实现快速幂模。

喜欢这篇文章的朋友可以关注我的博客http://zwgeek.com