crt.cpp

RSA加密中的大整数运算

int euclid(int d,int f)  //欧几里得算法(最大公约数)
{
 int m = d;
 int y = f;
 int r;
 while(1){
  if(y==0) return m;
  r = m % y;
  m = y;
  y = r;
 }
}


int extended_euclid(int d,int f)//扩展欧几里得算法(求逆元)
{
	int x1,x2,x3,y1,y2,y3,gcd,ni;
	x1=1;
	x2=0;
	x3=f;
	y1=0;
	y2=1;
	y3=d;
	int q,t1,t2,t3;
	while(1)
	{
/*		if(y3==0)
		{
			gcd=x3;
			ni=0;
			break;
		}*/
		if (y3==1)
		{
			gcd=y3;
			ni=y2;
			if(ni<0) ni+=f;
			return ni;
		}
		q=x3/y3;
		t1=x1-q*y1;
		t2=x2-q*y2;
		t3=x3-q*y3;

		x1=y1;
		x2=y2;
		x3=y3;

		y1=t1;
		y2=t2;
		y3=t3;
	}
	
/*	if (ni==0)
	{
		cout<<"gcd("<<d<<","<<f<<")="<<gcd<<endl;
		cout<<"无逆元"<<endl;
	}
	if (ni!=0)
	{
		cout<<"gcd("<<d<<","<<f<<")="<<gcd<<endl;
		cout<<d<<"^-1mod"<<f<<"="<<ni<<endl;
	}*/
}

string crtmain(char *p)
{
	int n=30,i,k,j;
	int *b=new int[n];
	int *m=new int[n];
	int *y=new int[n];
/*
	cout<<"输入方程的个数：";
	cin>>n;

	cout<<"请分别输入方程的b值和模m"<<endl;
	for(i=0;i<n;i++)
	{
		cin>>b[i];
		cin>>m[i];
	}*/
    
        int num=0;
		char temp[10];
		i=0,k=0;
		n=0;
        while(1)
        {
			while(p[i]<'0'||p[i]>'9')i++;
			j=0;
			while(p[i]>='0'&&p[i]<='9')temp[j++]=p[i++];
			temp[j]='\0';
            b[k]=atoi(temp);

			i+=3;
			j=0;
			while(p[i]>='0'&&p[i]<='9')temp[j++]=p[i++];
			temp[j]='\0';
            m[k++]=atoi(temp);
			n++;
			if(p[i]=='=')break;
         
        }   

	int M=1;
	for(i=0;i<n;i++)
	{
		M=M*m[i];
		for(int j=i+1;j<n;j++)
		{
			if(euclid(m[i],m[j])!=1)
			{
				cout<<"输入的m不是两两互素"<<endl;
				exit(0);
			}
		}
	}
	int x=0;
	for(i=0;i<n;i++)
	{
		y[i]=extended_euclid(M/m[i],m[i]);
		x=x+(b[i]*M*y[i]/m[i])%M;
	}
	x=x%M;
//	cout<<"方程组的结果为：x="<<x<<endl;
	delete []b;
	delete []m;
	delete []y;
	_itoa(x,temp,10);
      string result=temp;
	_itoa(M,temp,10);
	result+="mod";
	result+=temp;
	return result;
}