euclid.cpp

计算机网络安全中的DES加密解密算法

//用扩展欧几里德算法求k模z的乘法逆元v(若k,z互素，则存在v)。

#include <iostream.h>

void main()
{
	long k,z,v,g;
	long Euclid(long,long,long&);
	cout<<"输入整数k,z (0<k<z) : ";
	cin>>k>>z;
	g=Euclid(z,k,v);
	if (g!=1)
		cout<<k<<"没有模"<<z<<"的乘法逆元\n"
		<<k<<"与"<<z<<"的最大公约数为"<<g<<endl;
	else
		cout<<k<<"有模"<<z<<"的乘法逆元"<<v<<endl;
}

long Euclid(long z,long k,long& v)
{
	long a[3]={1,0,z},b[3]={0,1,k},t[3],q;
	int i;
	while (1)
	{
		if (b[2]==0)
		{
			v=b[2];
			return a[2];
		}
		if (b[2]==1)
		{
			if (b[1]<0)
				b[1]+=z;
			v=b[1];
			return b[2];
		}
		q=a[2]/b[2];
		for (i=0;i<3;i++)
		{
			t[i]=a[i]-q*b[i];
			a[i]=b[i];
			b[i]=t[i];
		}
	}
}