详解蒙哥马利算法

1 背景

在密码学中，最常见的一类基础运算大概就是模算术(Modular Arithmetic)了，特别地，模乘(Modular Multiplication)是其中最复杂的运算。而且在实际的密码算法中各个运算都是基于大数运算，正常的大数模乘运算计算和存储开销尤其大。以基于模16位数N运算为例，对于加法模运算，两个小于N的数a，b相加，要么a+b小于N，这时a+b的值就是最终模运算结果，如果a+b大于或等于N，则a+b-N即为最终模运算结果，而且a+b最多为一个17位的数，存储和计算开销都较小；但是如果是乘法模运算，a*b最大可以产生32位的数，存储空间直接翻倍，这时再对结果取余要么基于除法运算，要么进行多次减法运算，可以想象存储和运算开销都大大增加。蒙哥马利模乘算法正是基于此背景产生，借助该算法可以大大减小模乘运算开销。
2 原理讲解

蒙哥马利算法并不是一个独立得算法，而是三个相互独立又相互联系的算法集合，其中包括：

2.1 蒙哥马利模乘

先给出算法解决的问题描述，即：

1. 已知正整数 N，欲在不使用“除法运算”的条件下，对输入的两个整数a, b，计算 c = a*b mod N。

复制代码

模乘是为了计算a*b mod N，普通算法中，在计算模N时，利用的是带余除法，除法运算需要太多次乘法，计算复杂度较高，蒙哥马利算法的思想就是利用进制表示简化除法运算，转化成位运算。
蒙哥马利形式：为了计算a*b mod N，需要找一个R，然后使得a' ≡ a*R mod N，b' ≡ b*R mod N，这就是蒙哥马利形式（也称蒙哥马利域内的数）。其中R不是随便找的一个数，它需要满足两个条件：
1 R=2k > N，其中k是满足条件的最小正数，这个取法能保证除于R就相当于右移k位，相当于将除法运算转换为移位操作；
2 gcd(R, N) = 1，这使得必能求出后续所需要的m。
为了计算一开始的a*b mod N，需要用到上面的蒙哥马利形式，令X=a'b'，我们可以设计一个函数MontgomeryReduction(X, R, N)来计算XR-1 mod N，简单计算发现这个函数的计算结果为：

这样再调用一遍函数计算MontgomeryReduction(X1, R, N)就得到我们最终需要的结果X1*R-1 mod N = a*b mod N，称这个函数运算叫蒙哥马利约减算法，所以说，蒙哥马利约减的产生是为了蒙哥马利模乘计算服务的。
2.2 蒙哥马利约减

蒙哥马利算法的核心在于蒙哥马利约简，而且前面提到，蒙哥马利算法的主要思想是把取模运算变得简单，蒙哥马利约减是计算X*R-1 mod N，相当于X/R mod N，由之前约定可知R=2k，所以X/R = X>>k（X右移k位），但是X不一定被R整除，右移操作会抹掉X中的低位，这个不是精确计算，而是向下取整除法。为了使得右移位操作不损失精度，我们需要找一个m，使得X+m*N是R的倍数，在模N意义下X+m*N ≡ X mod N，所以增加mN在模N运算下不影响最终结果，但是却能使得X+m*N可以直接进行右移运算且不损失精度，接下来重点分析如何求m。

根据R的定义，gcd(R, N) = 1，根据扩展欧几里德算法如下图，存在R'和N'，使得RR' – NN' = 1，并且有00  IF E%2=0    C=C*C % N    E=E/2  ELSE    D=D*C % N    E=E-1RETURN D继续分析会发现，要知道E何时能整除2，并不需要反复进行减一或除二的操作，只需验证E的二进制各位是0还是1就可以了，从左至右或从右至左验证都可以，从左至右会更简洁，设E=Sum[i=0 to n](ei*2^i)，0