zhouyun1.cpp

几种模幂算法

#include <iostream.h>
void main()
{
	int x,y,p;
	int i,j,k;
	int l,m,n;
	int a,c,b;
	int r,e,d,f,g;
	int R[10000];
	int Q[10000];
	cout<<"x=";cin>>x;
    cout<<"y=";cin>>y;
	cout<<"p=";cin>>p;
	cout<<"请输入指数K:";cin>>k;
	l=1;
	i=1;
	a=x;
	n=0;
	for(j=1;j<=k;j++)
	{
		l=2*l;
	}
	/*-------建立R[]-------*/
	R[0]=1;
	for(i=1;i<=l-1;i++)
	{
		a=x;
		b=i;
		g=1;
		while(b!=0)
		{
           f=b%2;
		   if(f==0)
		   {
			   b=b/2;a=a*a%p;
		   }
		   else 
		   {	
			   b=b-1;g=(a*g)%p;
		   } 
		}
        R[i]=g;
	}
	i=i-1;
	/*------将y表示为2的K次方进制数------*/
	n=0;
	while(y!=0)
	{
		e=y%l;
		Q[n++]=e;
		y=y/l;
	}
	n=n-1;
	/*------计算x的y次方模p的值------*/
    r=1;
	i=n;
	while(i>=0)
	{
		for(j=1;j<=k;j++)
		{
			r=r*r;
            r=r%p;
		}
	    c=Q[i];
	    r=(r*R[c])%p;
        i=i-1;
	}
	cout<<"x"<<"的"<<"y次方"<<"模p"<<"的值为"<<r<<endl;
}