题目:
1）欧几里德算法求a，b的最大公约数；
2）扩展的欧几里德算法，求出gcd(a,b)和满足gcd(a,b)=ax+by的整数x和y；
3）求解模线性方程 ax ≡ b (mod n) 其中n>0；
4）求解模线性方程组(中国余数定理)；
5）模取幂运算，计算ab mod n （a,b>1032）；
6）Miller-Rabin随机性素数测试算法（要求判定n>1016）；
#include<iostream.h>
#define num 3 //中国剩余定理中应用
#define w 1000 //中国剩余定理中应用
//-------------------------------目录函数------------------------------
void menu()
{
cout<<"请选择："<<endl
<<"------------------------------------------------------------------------"<<endl
<<"(1) 欧几里德算法求a，b的最大公倍数:"<<endl
<<"(2) 扩展的欧几里德算法，求出gcd(m,n)和满足gcd(m,n)=am+bn的整数a和b"<<endl
<<"(3) 求解模线性方程 ax ≡ b (mod n) 其中n>0"<<endl
<<"(4) 求解模线性方程组(中国余数定理)"<<endl
<<"(5) 模取幂运算，计算ab mod n （a,b>1032）"<<endl
<<"(6) Miller-Rabin随机性素数测试算法（要求判定n>1016"<<endl
<<"------------------------------------------------------------------------"<<endl;
}
void swap(int *a, int *b)
{
int c=*a;
*a=*b;
*b=c;
}
//--------------------------欧几里德算法-----------------------------------
void GCD(int a,int b)
{
int c;
if(a<b)
swap(&a,&b);
{
if(b==0)
cout<<"GCD(a,b)="<<b<<endl;
else
{
for(c=a%b; c>0;c=a%b)
{
a=b;
b=c;
}
cout<<"GCD(a,b)="<<b<<endl
<<"------------------------------------------------------------------------"<<endl;
}
}
}
//--------------------------扩展欧几里德算法---------------------------------
void ex_GCD(int m,int n)
{
int c,d,a,b;
int a1=b=1;
int b1=a=0;
if(m<n)
{
int temp=m;m=n;n=temp;
}
c=m;d=n;
int q=c/d;
int r=c%d;
while(r!=0)
{
c=d; d=r;
int temp=a1;
a1=a; a=temp-q*a; temp=b1;
b1=b; b=temp-q*b;
q=c/d; r=c%d;
}
cout<<"ex-GCD(m,n)="<<d<<endl;
cout<<a<<"*m"<<" + "<<b<<"*n"<<" ="<<d<<endl
<<"------------------------------------------------------------------------"<<endl;
}
//----------------------中国剩余定理-------------------------------
void chinese_remainder(int m[],int u[])
{
int k,ch_va,count=0,x;
cout<<"X"<<"≡"<<"m[i]"<<"(mod"<<"u[i])"<<endl;
for(ch_va=0;ch_va<w;ch_va++)
{
k=0;
while(k!=0)
{
x=(ch_va%u[k++]==m[k++]&&ch_va%u[k++]==m[k++]);
}
if(x==1)
{
cout<<ch_va<<" "; count++;
if(count==5)
cout<<endl;
}
}
cout<<"------------------------------------------------------------------------"<<endl;
}
//--------------------主函数应用--------------------------------
void main()
{
int n,a,b;
char k='y';
menu();
while(k=='y')
{
cin>>n;
switch(n)
{
case 1:
cout<<"请输入a, b的值：";
cin>>a>>b;
GCD(a,b);
break;
case 2:
int m,n;
cout<<"输入m,n两个数字"<<endl;
cin>>m>>n;
ex_GCD(m,n);
break;
case 4:
int i,M[num],U[num];
cout<<"X"<<"≡"<<"m[i]"<<"(mod"<<"u[i])"<<endl
<<"请输入m[i]的值："<<endl;
for(i=0;i<num;i++)
cin>>M[i];
cout<<"请输入u[i]的值:"<<endl;
for(i=0;i<num;i++)
cin>>U[i];
chinese_remainder(M,U);
break;
}
cout<<"是否继续 y or n?";
cin>>k;
cout<<"------------------------------------------------------------------------"<<endl;
}
}
问中国剩余定理部分出了什么错?在问一下5）模取幂运算，计算ab mod n （a,b>1032）；
6）Miller-Rabin随机性素数测试算法（要求判定n>1016）；的做法?
谢谢!
