一.试验目的
通过C++实现中国剩余定理算法的实现。二.试验原理
设正整数 m1，m2，...，mk 两两互素，对任意整数 a1，a2，...，ak，一次 同余方程组： 在模m意义下有唯一解，该解可表示为：三.所用miracl函数
（1）copy(msum,temp3); ——>用法：将一个大数赋值给另一个大数，temp3=msum； （2）divide(x,y,z); ——>用法：z=x/y，注意：运算结束后x=x(mod y)； （3）xgcd(big x,big y,big temp1,big temp1,big temp1); ——>用法：temp1=1/x mod y，y是一个素数； （4）multiply(temp1,a,temp2); ——>用法：两个大数相乘，temp2=temp1*a； （5）add(z,y,x); ——>用法：x=y+z； （6）cotnum(x,stdout); ——>将大数 x 输出到屏幕；四.算法求解思路
求解一次同余方程组： （1）判断正整数m1，m2，...，mk 是否两两互素；是，则继续，否，则跳出。 （2）计算Mj^(-1) (mod mj)。 （3）计算xj，xj为Mj*Mj^(-1)*a (mod m)。 （4）计算x=x1+x2+...+xk (mod m)。五.代码实现
extern "C" { #include "miracl.h" } #include<stdio.h> #include<math.h> #include<string.h> int main(){ big m[100],a[100],temp1,temp2,msum,temp3,x,temp4; int i,k,num=0; char m_str[100]={0},a_str[100]={0}; miracl *mip=mirsys(30,10); for(i=0;i<100;i++){m[i]=mirvar(0);a[0]=mirvar(0);} temp1=mirvar(0); temp2=mirvar(1); msum=mirvar(1); temp3=mirvar(0); x=mirvar(0); temp4=mirvar(1); printf("**********欢迎来到中国剩余定理算法**********\n"); printf("请输入方程的个数："); scanf("%d",&num); for(i=0;i<num;i++){ if(i==0){gets(a_str);} for(k=0;k<100;k++){m[i]=mirvar(0);a[i]=mirvar(0);m_str[i]=0,a_str[i]=0;} printf("请输入方程的参数：a[%d]=",i); gets(a_str); printf("请输入方程的参数：m[%d]=",i); gets(m_str); cinstr(a[i],a_str); cinstr(m[i],m_str); } //判断m1,m2...是否互素,length=2 for(i=0;i<num;i++){ for(k=i+1;k<num;k++){ egcd(m[i],m[k],temp1); if(compare(temp1,temp2)!=0){printf("不能直接利用中国剩余定理\n");printf("**********程序结束**********\n");return 0;} } } //计算msum=m1*m2*... for(i=0;i<num;i++)multiply(msum,m[i],msum); for(i=0;i<num;i++){ copy(msum,temp3); divide(temp3,m[i],temp2);//计算temp2=Mi xgcd(temp2,m[i],temp1,temp1,temp1);//计算temp1=Mi(-1) multiply(temp2,temp1,temp2); multiply(temp2,a[i],temp2);//temp2=Mi*Mi(-1)*a[i] add(temp2,x,x); } powmod(x,temp4,msum,x); printf("得出的结果为x="); cotnum(x,stdout); //计算出x=x(mod m) printf("**********程序结束**********\n"); return 0; }六.实验结果
