gaoji.cpp

在现代密码学中

#include<iostream.h>
#include<math.h>
int fun(int x,int y)//求最大公因数
{
	int flag,data;
	if(x<y)
	{
		flag=x;
		x=y;
		y=flag;
	}
	do
	{
		data=x%y;
		x=y;
		y=data;
	}while(y!=0);
	return x;
}
void inv(int a,int m)//求逆元
{
	int k,q,r,s0,s1,s2;
    int t0,t1,t2;
	int c,d;
	c=a;//临时变量c保存a的值
	d=m;//临时变量d保存m的值
	s0=t1=1;
	s1=t0=0;
	if(a<m)//交换a和m，用大数去除小数
	{
		k=a;
		a=m;
		m=k;
	}
	while(r!=0)//递归法求s,t
	{
		q=a/m;
		r=a%m;
        s2=s0-q*s1;
		t2=t0-q*t1;
		a=m;
		m=r;
		s0=s1;
		s1=s2;
		t0=t1;
		t1=t2;
	}
	cout<<"s0="<<s0<<endl;
	cout<<"t0="<<t0<<endl;
	//*输入的两个数有大小之分，但s0始终为大数的系数；t0始终为小数的系数*//
	//*****当a小于m时*****//
	if(c<d)
	{
		if(t0<0)
			cout<<"逆元为："<<d-(int)fabs(t0)%d<<endl;
		else
			cout<<"逆元为："<<t0%d<<endl;
	}
	//*****当a大于m时*****//
	else if(c>d)
	{
		if(s0<0)
			cout<<"逆元为："<<d-(int)fabs(s0)%d<<endl;
		else
			cout<<"逆元为："<<s0%d<<endl;
	}
}
void main()
{
	while(1)
	{
		int a,m,b;
	    int s0(1),t0(0);
	    cout<<"请输入一个正整数（a>0）：";
	    cin>>a;
	    cout<<"请输入模（m>0）：";
	    cin>>m;
	    b=fun(a,m);
	    if(b==1)//判断输入的两个数是否互素
		{
		    inv(a,m);
		}
	    else
		    cout<<"两个数不互质，请重新输入!"<<endl;
		cout<<endl;
	}
}