蒙哥马利算法的概念与原理

　　蒙哥马利（Montgomery）幂模运算是快速计算a^b%k的一种算法，是RSA加密算法的核心之一。

　　蒙哥马利模乘的优点在于减少了取模的次数（在大数的条件下）以及简化了除法的复杂度（在2的k次幂的进制下除法仅需要进行左移操作）。模幂运算是RSA 的核心算法，最直接地决定了RSA 算法的性能。

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

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

　　蒙哥马利乘模，是用来计算x⋅y （mod N）

　　蒙哥马利约减，是用来计算t⋅ρ−1 （mod N）

　　蒙哥马利幂模，是用来计算xy （mod N）

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

　　基本概念

　　梳理几个概念，试想一个集合是整数模N之后得到的

　　ZN={0，1，2，⋯，N−1}

　　注：N在base-b进制下有lN位。 比如10进制和100进制，都属于base-10进制，因为100=102，所以b=10。在10进制下，667的lN=3这样的集合叫做N的剩余类环，任何属于这个集合Z的x满足以下两个条件：

　　1. 正整数

　　2. 最大长度是lN

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

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

　　对于加法运算，如果计算x±y （mod N） （0≤x，y＜N），试想自然数集上的 x±y

　　0≤x+y≤2⋅（N−1）

　　−（N−1）≤x−y≤（N−1）我们可以简单的通过加减N来实现从自然数到剩余类集的转换

　　另外一类是乘法操作，也就是x⋅y （mod N）（0≤x，y＜N），那么

　　0≤x⋅y≤（N−1）2如果在自然数集下，令t=x⋅y，那么对于modN我们需要计算

　　t−（N⋅⌊t/N⌋）加减操作很简单，具体的算这里就不细说了，我们用ZN−ADD 来代表剩余类环上的加法操作。既然我们可以做加法操作，那么我们就可以扩展到乘法操作，算法如下

　　但是这并不是一个好的解决方案，因为通常来说，我们不会直接做w位乘w位的操作，这个后面会用蒙哥马利的乘法来代替解决。

　　对于取模操作，一般有以下几种方法

　　1，根据以下公式，来计算取模操作

　　t−（N⋅⌊t/N⌋）

　　这种解法有以下特征

　　整个计算过程是基于标准的数字表示

　　不需要预计算（也就是提前计算一些变量，以备使用）

　　涉及到一个除法操作，非常费时和复杂

　　2，用Barrett reduction算法，这篇文章不细说，但是有以下特征

　　基于标准的数字表示

　　不需要预计算

　　需要2⋅（lN+1）⋅（lN+1） 次数乘运算

　　3，用蒙哥马利约减，也就是下面要讲的算法，有以下特征

　　不是基于标准的数字表示（后文中有提到，是基于蒙哥马利表示法）

　　需要预计算

　　需要2⋅（lN）⋅（lN） 次数乘运算