蒙哥马利乘法原理蒙哥马利乘法原理

引子

加密算法中，有很多大数（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中，需要用到这样的模幂运算，也就是多次的模乘运算，这时蒙哥马利乘法相较于直接的模乘就会提升更多的性能。
结语上面简单介绍了蒙哥马利乘法的原理和应用，针对该算法的硬件和软件实现，前人进行了大量的优化研究工作，基本方向是优化循环体中的乘法运算，加法运算以及循环体外的减法运算，但是万变不离其宗，只要理解了原理，再去看论文就会轻松许多。