RSA中的高次模算法

Question

2) 做高次模运算
//****************************
// 这个函数用来做高次模
//****************************
long int CRSADlg::HightMod(long int iBottomNumber,long int iExponent,long int iMod)
{
  long int iValueMessageAfterCompute=1;
  long int iValueMessage=iBottomNumber;
  long int iKey=iExponent;
  //把key以2进制的形式进行移位乘用
  while(iKey)
  {
    if(iKey&1) iValueMessageAfterCompute=(iValueMessageAfterCompute*iValueMessage)%iMod;
    //高位右移
    iKey>>=1;
    iValueMessage=(iValueMessage*iValueMessage)%iMod; 
  }
  return iValueMessageAfterCompute;
}原理：
①(a*b)%n=((a%n)*b)%n 
②(ab)%n
当b为偶数的时候等于:ab/2%n
当b为奇数的时候等于:ab/2*a%n
③通常将b转化为二进制，二进制位为1表示am=(am/2)2*a，即m奇数；二进制位为0表示am=(am/2)2，即m偶数；
④result表示余数；迭乘的起始值为1；a0 % n=1；
想不明白

Answer 1

这是蒙哥玛利模幂算法,那两句想看懂就要去看他的数学推导了.模幂运算是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 这样，模幂运算就转化成了一系列的模乘运算。