蒙哥马利幂模运算

简介

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

特点及原理

蒙哥马利模乘的优点在于减少了取模的次数（在大数的条件下）以及简化了除法的复杂度（在2的k次幂的进制下除法仅需要进行左移操作）。模幂运算是RSA 的核心算法，最直接地决定了RSA 算法的性能。 针对快速模幂运算这一课题，西方现代数学家提出了大量的解决方案，通常都是先将幂模运算转化为乘模运算。 例如求D=C^15%N 由于：a*b % n = (a % n)*(b % n) % n 所以令： C1 =C*C % N =C^2 % N C2 =C1*C % N =C^3 % N C3 =C2*C2 % N =C^6 % N C4 =C3*C % N =C^7 % N C5 =C4*C4 % N =C^14 % N C6 =C5*C % N =C^15 % N 即：对于E=15的幂模运算可分解为6 个乘模运算，归纳分析以上方法可以发现： 对于任意指数E，都可采用以下算法计算D=C**E % N： D=1 WHILE E>=1 IF E%2=0   C=C*C % N   E=E/2 ELSE   D=D*C % N   E=E-1 RETURN D