蒙哥马利算法(Montgomery Algorithm)|蒙哥马利约简、模乘
模乘是为了计算ab(mod M)。普通算法中，在计算模M时，利用的是带余除法，除法运算需要太多次乘法，计算复杂度较高
蒙哥马利算法的思想就是利用进制表示简化除法运算，转化成位运算。
给定大数 a, b. 素数模 m
目的是求 Z = ab(mod m)
转化为蒙哥马利域算式:
先计算 aR(mod m), bR(mod m), 其中R=2^k, k=log2(m)
第一次蒙哥马利约简:
Z’= aR * bR * R^-1 (mod m) = abR(mod m) (1)
第二次蒙哥马利约简:
Z = Z’ * R^-1(mod m) = abR * R^-1 (mod m) = ab (mod m) (2)
第二次约简后即可求出最终的结果.
蒙哥马利约简
核心思想是利用进制移位简化除法运算
Montgomery reduction(X,R,m):
参数:
- X ———– 输入操作数, 比如对应第一次蒙哥马利约简, aR*bR(mod m)即为X
- R ———– 根据模m选定的数R, 即上面的R
- m ———– 模 m
步骤:
- 计算m’=m^-1 (mod R), (m’ 也被称为mp), n = Xm’(mod R)
- 计算y=(X+nm)/R (mod m) — 将X+nm 右移k位得到最终结果y ( R=2^k, k=log2(m) )
分析:
- (X+nm)/R (mod m) === X * R^-1 (mod m) ?
同余运算, 因为 nm/R (mod m) === 0, 所以相等
- n 是怎么得来的 ?
这里n要满足算式:
X+nm === 0 (mod R) 只有这样, (X+nm)/R 才能将除法转化为进制移位计算
根据R的定义, R要满足 gcd(R, m)=1, 即 R和m之间最大公约数是1, 即R和m 互质. 这里因为 m 一般为素数, 而R=2^k所以这个条件是满足的,
根据扩展的欧几里得算法:
RR′−mm′=1 即 mm’=RR’-1
X+nm === 0 (mod R)
Xm’ + nmm’ === 0 (mod R)
Xm’ + n(RR’-1) === 0 (mod R)
Xm’ - n === 0 (mod R)
n === Xm’ (mod R)
蒙哥马利预计算
从上面的约简过程看, 预计算最重要的参数是m’(mp), 同时 R R^-1 (mod m) R^2 (mod m) 也是需要预计算的
即一次ab(mod m)需要两次蒙哥马利约简, 且输入其实不是ab 而是 a’b’ = ab * R^2, 所以需要提前计算 abR^2的值.
注意一个数的逆只有在取模时才有意义, 没有模哪来的逆, 逆也是对某个模而言的, 换了模,这个数的逆就变成另一个值了