蒙哥馬利冪模運算

蒙哥馬利(Montgomery)冪模運算是快速計算a^b%k的一種算法，是RSA加密算法的核心之一。

基本介紹

• 中文名：蒙哥馬利冪模運算
• 外文名：Montgomery
• 性質：算法
• 特點：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>0

IF E%2=0

C=C*C % N

E=E/2

ELSE

D=D*C % N

E=E-1

RETURN D

繼續分析會發現，要知道E 何時能整除 2，並不需要反覆進行減一或除二的操作，只需驗證E 的二進制各位是0 還是1 就可以了，從左至右或從右至左驗證都可以，從左至右會更簡潔，

設E=Sum[i=0 to n](E*2**i)，0<=E<=1

則：

D=1

FOR i=n TO 0

D=D*D % N

IF E=1

D=D*C % N

RETURN D這樣，模冪運算就轉化成了一系列的模乘運算。

C++實現

inline unsigned __int64 MulMod(unsigned __int64 a, unsigned __int64 b, unsigned __int64 n)

{

return a * b % n;

}

/*

模冪運算，返回值 x=base^pow mod n

*/

unsigned __int64 PowMod(unsigned __int64 base, unsigned __int64 pow, unsigned __int64 &n)

{

unsigned __int64 a=base, b=pow, c=1;

while(b)

{

while(!(b & 1))

{

b>>=1; //a=a * a % n; //

a=MulMod(a, a, n);

} b--; //c=a * c % n; //

c=MulMod(a, c, n);

} return c;

}