模重复平方计算法.cpp

模重复平方法

#include<iostream.h>
unsigned long fun(unsigned long b,unsigned long m,unsigned long n)
{
	int a1[100];  //保存转换后的二进制数
	unsigned long a[50];
	long max;
    for(int i=0;i<100;i++)  //将n转换成二进制
	{
		a1[i]=n%2;   
		cout<<a1[i];
		n=n/2;
		if(n==0)
		{
			max=i;  //max为二进制的位数
			break;
		}
	}
	cout<<endl;
	a[0]=1;     
	for(int j=0;j<=max;j++)  
	{ 
		if(j==0)           
		{
			if(a1[j]==0)
			{
				a[0]=1;
				b=b*b%m;  //下一个b
			}
			if(a1[j]==1)
			{
				a[j]=b%m;  //a
				b=b*b%m;
				cout<<a[j]<<" ";
			}
		}
		else
		{
			if(a1[j]==0)   
			{
				a[j]=a[j-1];
				b=b*b%m;
			}
			if(a1[j]==1)
			{
				a[j]=a[j-1]*b;
				a[j]=a[j]%m;
			    b=b*b%m; 
			}
			cout<<a[j]<<" ";
		}
	}
	return a[j-1];
}
void main()
{
	unsigned long b,m,n,q;
	cout<<"请输入数据：m=";
	cin>>m;
	cout<<endl;
	cout<<"b=";
	cin>>b;
	cout<<endl;
	cout<<"n=";
	cin>>n;
	cout<<endl;
    q=fun(b,m,n);
	cout<<"结果为："<<q<<endl;
}