引子

加密算法中，有很多大数（256bits~2048bits）的运算，基础之一便是类似于求 的值。在这个运算中，有乘法和取模，而取模需要除法，这在计算机中是极为耗时的，为了让计算机可以快速的执行取模运算，我们需要将除法转变为计算机擅长的运算。

普通人的思路

在计算机的世界里，首先一个很自然的想法就是将数据表示成二进制：

则可写为：

如此，便可用如下程序实现该过程：

for k-1 to 0
    C*=2;
    C+=a[i]*B;
endfor
return C % N;

上述过程只是将大数的乘法简化为乘2和加法，乘2即左移。但是还有一个问题，因为循环中有乘2的操作，所以循环运算的中间值会超过k比特，会占用更多的资源。利用取模运算的性质，我们可以把取模运算放入循环体中：

for k-1 to 0
    C*=2;
    C=C%N;
    C+=a[i]*B;
    C=C%N;
endfor
return C;

如此中间值就不会超过k+1比特，这样就剩下取模运算没有化简了。考虑到我们的数是以二进制表示的，在运算过程中，不论是 还是 ，的值都小于，因此取模运算可以变成一个比较和减法：

for k-1 to 0
    C*=2;
    C=(C>=N)? C-N,C;
    C+=a[i]*B;
    C=(C>=N)? C-N,C;
endfor
return C;

事情看起来非常美好，取模没有了，乘法也变成了移位。但是该方法需要循环的次数太多。如想要减少循环次数，就不能用二进制表示，而如果我们用进制表示，那么循环体中的取模就不能再用减法取代了，因为可能大于。前方是一条死路，要想获得更好的性能，只有另辟蹊径。

蒙哥马利的想法

考虑到的化简最简单的就是减法，而这需要。想要减少循环次数，就需要进制表示。为了满足这两个条件，我们考虑这样一种算法：

其中

为以进制表示时的位数
代入上式即得：

程序实现：

for k-1 to 0
    C+=a[i]*B;
    C/=r;
endfor
return C % N;

这样的实现是不准确的，因为C不一定是r的倍数，当C/=r时，会得到不准确的结果。因此，在计算C/=r的之前，需要先加上一个值，使C可以被r整除，但加上的值又能不影响取模的最终结果，因此这个值应为N的整数倍。
不妨设其为，则:

for k-1 to 0
    C+=a[i]*B+q*N;
    C/=r;
endfor
return C % N;

我们的要求是，即，其中为以进制表示时的个位数的值。很容易看出其中一个q的解为，因此上述程序可改为：

c0= 0;
b0= B % r;
n0= N % r;
w = -n0^(-1) % r;
for k-1 to 0
    q=(c0+a[i]*b0)*w;
    q=q % r;
    C+=a[i]*B+q*N;
    C/=r;
    c0=C % r;
endfor
return C % N;

最后跳出循环时，C的值小于2N，因此：

c0= 0;
b0= B % r;
n0= N % r;
w = -n0^(-1) % r;
for k-1 to 0
    q=(c0+a[i]*b0)*w;
    q=q % r;
    C+=a[i]*B+q*N;
    C/=r;
    c0=C % r;
endfor
return (C>=N)? C-N,C;

这样，我们就把取模运算变换成了移位，乘法和加减。b0，n0和w都可以预计算，循环次数k也可以调整，例如数据A,B为1024bits，用二进制表示计算时k=1024，用进制表示时，k=16，只不过循环中的乘法变成了64位与1024位的乘法。在对该算法进行优化的时候可以选取适当的k和r。
这个计算机可以较为轻松的处理的算法，，就是广泛使用的蒙哥马利算法，我们记为，那么怎么把它和联系起来呢？很简单，多用几次就行了：

前两步称为进入蒙哥马利域，最后一步称为退出蒙哥马利域，又叫蒙哥马利约减。从步骤上看，我们好像把事情搞复杂了，本来一个乘法取模的运算，我们用了四个蒙哥马利乘法，其实不然，一方面蒙哥马利乘法是针对计算机操作优化过的，另一方面，在RSA中，需要用到这样的模幂运算，也就是多次的模乘运算，这时蒙哥马利乘法相较于直接的模乘就会提升更多的性能。

结语

上面简单介绍了蒙哥马利乘法的原理和应用，针对该算法的硬件和软件实现，前人进行了大量的优化研究工作，基本方向是优化循环体中的乘法运算，加法运算以及循环体外的减法运算，但是万变不离其宗，只要理解了原理，再去看论文就会轻松许多。