密码学-模幂运算

模幂运算是对给定的整数p、n、a，计算 $a^{n} mod \; p$ ，这个运算在密码学中应用极为普遍，RSA、ElGamal、DH交换等重要密码方案中都涉及模幂运算。

1、算法原理

模重复平方计算法：

$r\equiv (ab)(mod\; m)\equiv (a(mod\; m)) (b(mod\; m))(mod\; m)$

算法步骤：

①将n表示为二进制， $n=n_{r}n_{r-1}...n_{1}n_{0}$ ，用一个数组保存n的各个数位，n共有r+1位。

②循环计算（用数组b保存所有中间结果）：先循环计算一系列结果：a^2 mod p，a^4 mod p，a^8 mod p，…，再把指数n的二进制表示中取值为1的位对应的a的幂相乘，即可得到最终结果。

2、代码实现

int main(int argc, char *argv[])
{   int n,a,p;
	int nn[30],aa[30],bb[30]; 
	
	cout<<"please input a and n: ";
	cin>>a; // 将键盘输入的值赋给a
	cin>>n;
	cout<<"Input a prime, p= ";
	cin>>p;
	cout<<endl;
	//将指数n表示为二进制
	int temp,num,r;
	int i=0;
	temp=n;
	while(temp != 0) 
	{	num = temp%2;
		nn[i] = num;
		i++;
		temp = temp/2;
	}
	r=i-1; 
	cout<<"指数的二进制表示为: ";
	for (num=i-1;num>=0;num--) //输出指数的二进制
		cout<<nn[num]<<" ";
	// bb[]中存放 a%p a^2%p a^4%p a^8%p ……的值
	aa[0] = a;
	bb[0] = a;
	for(i=0;i<n/2;i++) // 不需要循环n次，最终计算结果为
	{	aa[i+1] = (aa[i]*aa[i])%p;
		bb[i+1] = aa[i+1];
	}
    cout<<endl;
	cout<<"a%p a^2%p a^4%p …的值: ";
	for (num=i-1;num>=0;num--) //输出
		cout<<bb[num]<<"  ";
	// 实际运算
	int x=1;
	for(i=0;i<r+1;i++)
	{	if (nn[i]==1)  x=(x*bb[i])%p;		
	}

	cout<<endl<<"the result is:";
	cout<<x<<endl;
	cin>>i; 
	return 0;
}