特點及原理
蒙哥馬利模乘的優點在於減少了取模的次數（在大數的條件下）以及簡化了除法的複雜度（在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;
}
