test.cpp

该程序可以很好的实现大整数幂同余的算法

#include<iostream.h>
#include<iomanip.h>
#include<math.h>
void main()
{
	while(1)//改变输入进行循环
	{
		int b,m,p,num,temp;
	    double q;
	    cout<<"输入底数b为：";
	    cin>>b;
	    cout<<"输入模m为：";
	    cin>>m;
	    cout<<"输入指数num为：";
	    cin>>num;
        temp=num;//将num的值赋给临时变量temp,用于最后的输出
	    q=log(num)/log(2);//对num取以2为底的对数，然后赋给q
        p=(int)q+1;//取整的结果赋给变量p，用于循环
	    int i,n[20],data;
	    while(num!=0)//取num除2后的余数
		{
		    for(i=0;i<p;i++)
			{
			    data=num/2;
		        n[i]=num%2;
		        num=data;
			}
		}
	    cout<<"将指数转化为二进制数为：";
	    for(i=0;i<p;i++)
		    cout<<n[p-i-1]<<setw(2);//将余数反转输出，将十进制数转化为二进制数
	    cout<<endl;
	    int a=1,d[20],c[20];//数组d中存放每步计算的b的平方，数组c中存放每步计算的a的值
	    d[0]=b*b;//初始化d[0]
        c[0]=a*(int)pow(b,n[0]);//初始化c[0]
	    cout<<"运用模重复平方法，依次计算如下："<<endl;
        //**********以下是第一步计算**********
        cout<<"n[0]="<<n[0]<<","<<setw(2);
	    cout<<"计算："<<setw(2);
        if(c[0]<m)//如果a的值小于模m，则输出a;否则输出a取余m
		{
		    cout<<"a[0]="<<c[0]<<","<<setw(2);
		}
	    else 
		{
	        cout<<"a[0]="<<c[0]%m<<","<<setw(2);
		    c[0]=c[0]%m;//取余后的值赋给a，用于下一步计算
		}
        if(d[0]<m)//如果b的值小于模m，则输出b;否则输出b取余m
		{
		    cout<<"b[1]="<<d[0]<<setw(2);
		}
	    else
		{
		    cout<<"b[1]="<<d[0]%m<<setw(2);
		    d[0]=d[0]%m;//取余后的值赋给b，用于下一步计算
		}
	    cout<<"("<<"mod "<<m<<")"<<endl;
        //**********以下是第二步至倒数第二步计算**********
        for(i=1;i<p-1;i++)
		{
		    c[i]=c[i-1]*(int)pow(d[i-1],n[i]);
		    d[i]=d[i-1]*d[i-1];
		    cout<<"n["<<i<<"]="<<n[i]<<","<<setw(2);
            cout<<"计算："<<setw(2);
		    if(c[i]<m)
			{
			    cout<<"a["<<i<<"]="<<c[i]<<","<<setw(2);
			}
		    else 
			{
	            cout<<"a["<<i<<"]="<<c[i]%m<<","<<setw(2);
			    c[i]=c[i]%m;
			}
	        if(d[i]<m)
			{
		        cout<<"b["<<i+1<<"]="<<d[i]<<setw(2);
			}
	        else
			{
		        cout<<"b["<<i+1<<"]="<<d[i]%m<<setw(2);
			    d[i]=d[i]%m;
			}
		    cout<<"("<<"mod "<<m<<")"<<endl;
		}
        //**********最后一步计算(不对b进行计算)**********
	    c[p-1]=c[p-2]*(int)pow(d[p-2],n[p-1]);
	    cout<<"n["<<p-1<<"]="<<n[p-1]<<","<<setw(2);
        cout<<"计算："<<setw(2);
	    if(c[p-1]<m)
		{
		    cout<<"a["<<p-1<<"]="<<c[p-1]<<setw(2);
		} 
	    else 
		{
	        cout<<"a["<<p-1<<"]="<<c[p-1]%m<<setw(2);
		    c[p-1]=c[p-1]%m;
		}
	    cout<<"("<<"mod "<<m<<")"<<endl;
	    cout<<"最后，计算出"<<endl;
	    cout<<b<<"的"<<temp<<"次方和"<<c[p-1]<<"模"<<m<<"同余."<<endl;
		cout<<endl;
	}
}
//运行结果中的等号为模的符号