csd.cpp

一个中国剩余定理的简单算法,密码学基础算法

/******************************************************************
** 文件名: 求解中国剩余定理
** Copyright (c) 2007 贵州大学计算机软件理论研究所
** 创建人: 王珽
** 日  期: 2007-11-9
** 修改人:
** 日  期:
** 描  述:
**
** 版  本:
**-------------------------------------------------------------------
*******************************************************************/
#include <iostream.h>
#include <math.h>
#include <stdio.h>

//求同余式中所有模的乘积
int Get_M(int mo[], int num)
{
	int i,mult=1;
	for(i=0; i<num; i++)
		{
			mult*=mo[i];
		}
	cout << endl <<"同余式中所有模的乘积为："<< mult << endl;
	return mult;
}

//求出同余式中各个模node[i]所对应的Mi
int * Get_Mi(int mo[], int mult, int num)
{
	int j, *a;
	a=new int[num];
	for(j=0; j<num; j++)
		{
			a[j]=mult/mo[j];
		}
	/*输出mode[i]对应的各个Mi*/
	cout << endl <<"mode[i]对应的各个Mi为：" << endl;
	for(j=0; j<num; j++) 
		cout << a[j] <<" "<< endl;
	return a;
}

/*利用Extended Euclidean方法 求出各个Mi的模mi逆元(或者叫Mi在模mi下的乘法逆)
int * Get_Moni(int mn[], int mno[], int num)
{
	int i,j,*b;
	b=new int[num];
	for(i=0; i<num; i++)
	{
		if(mn[i]%mno[i]==1)
			{
				b[i]=1;
			}
		else
			{
				j=mn[i]%mno[i];
				b[i]=(mno[i]+1)/j;
			}
	}
	return b;
}*/

/*利用Euclidean方法 求出两个整数的最大公因子*/

int euclid(int a,int b)
{
	if(b==0) return a;
	else return(euclid(b,a%b));
}

/*利用Extended Euclidean方法 求出各个Mi的模mode[i]逆元(或者叫Mi在模mi下的乘法逆)*/

int * Ex_euclid(int mo[],int Mi_1[],int num)
{
	int a,b,t1,t2,q,r,temp;
	int i,*c;
	c=new int[num];
	for(i=0;i<num;i++)
	{
		a=mo[i]; 
		b=Mi_1[i]; 
		t1=0; 
		t2=1; 
		q=a/b;
		r=a-q*b;
		while(r > 0)
		{
			if(((t1-q*t2)%mo[i]) < 0) 
				temp=((t1-q*t2)%mo[i])+mo[i];
			else 
				temp=(t1-q*t2)%mo[i];
			t1=t2;
			t2=temp;
			a=b;
			b=r;
			q=a/b;
			r=a-q*b;
		}
		if(b!=1) 
			{cout<<Mi_1[i]<<"没有模"<<mo[i]<<"的逆元!"<<endl;}
		else 
			c[i]=t2;
	}
	/*输出各个Mi的模mode[i]逆元*/
	cout << endl <<"各个Mi的模mode[i]逆元为：" << endl;
	for(i=0; i<num; i++)
		cout << c[i] << " " << endl;
	return c;
}

void main()
{
	int i,N,M, X=0;
	int *mode, *Mi, *Moni, *b;
	cout << "请输入同余方程组中同余式的个数：";
	cin >> N;

	//建立动态数组
	mode = new int[N];
	Mi = new int[N];
	Moni = new int[N];
	b = new int[N];

	cout << endl << "输入各个同余式的系数："<<endl;
	for(i=0; i<N; i++)
		cin >> b[i];

	cout << endl << "输入各个同余式的模："<<endl;
	for(i=0; i<N; i++)
		cin >> mode[i];

	M = Get_M(mode, N); //调用函数Get_M() 求M
	Mi = Get_Mi(mode, M, N); //调用函数Get_Mi() 求各个Mi
	Moni = Ex_euclid(mode,Mi,N); //调用函数Ex_euclid() 求各个Mi的模mode[i]逆元
	for(i=0; i<N; i++) //求同余方程组的模 M 的唯一解X
	{
		X=b[i] * Mi[i] * Moni[i] + X;
	}
	cout << endl << "同余方程组的模 M 的唯一解为：" << X<<endl;
}