exeuclid.cpp

初学密码内容

//扩展欧几里德算法：在GF(p)中求一个数的乘法逆元

#include <iostream.h>
#include <conio.h>

class ExEuclid							//定义一个专为此算法的类 
{
	public:
		ExEuclid(int tm, int td);		//构造函数
		void ExecuteEE();				//算法具体实现函数
		int getId();					//获得所求数d的逆元
		int getGcdmd();					//获得模m与所求数d的最大公因式

	private:
		int A[3];						//保存（A1，A2，A3）这个三元组的数组
		int B[3];						//保存（B1，B2，B3）这个三元组的数组
		int m, d, id, gcdmd;			//分别是模m，所求数d，d的逆元，m与d的最大因子
};

ExEuclid::ExEuclid(int tm, int td)		//初始化三元组，tm、td分别为用户输入的m与d
{
	A[2] = m = tm;
	B[2] = d = td;
	A[0] = B[1] = 1;
	A[1] = B[0] = 0;
}

int ExEuclid::getId() { return id; }
int ExEuclid::getGcdmd() { return gcdmd; }

//算法说明：扩展欧几里德算法
//输入：三元组（A1，A2，A3）、（B1，B2，B3）（实际上是m与d）
//输出：d的逆元id，m与d的最大公因式gcdmd

void ExEuclid::ExecuteEE()
{
	while(1)
	{
		if(B[2] == 0) { gcdmd = A[2]; id = -1;  return; }				//没逆元
		if(B[2] == 1) { gcdmd = B[2]; id = (B[1]%m + m)%m; return; }	//找到成功退出（注意负数情况）
		
		int Q;								
		int T[3];						//T[]为暂存数组
		Q = A[2] / B[2];
		
		for(int i=0; i<3; i++)
		{
			T[i] = A[i] - Q*B[i];
			A[i] = B[i];
			B[i] = T[i];
		}
	}
}

void main()								//测试程序（求GF(mm)中dd的逆元最大公因式）
{
	int mm;
	int dd;
	cout<<"***正在运行GF(p)中求乘法逆元程序***"<<endl;
	cout<<endl<<"请输入GF(p)中的p值: ";
	cin>>mm;
	cout<<endl<<"请输入须求逆元的d值: ";
	cin>>dd;
	
	ExEuclid e(mm, dd);					//用输入数据申请一个对应类
	e.ExecuteEE();

	cout<<endl<<"p与d的最大公因数为: "<<e.getGcdmd()<<endl;
	
	if(e.getId() == -1)					//找不到逆元
	{ 
		cout<<endl<<"此d值没逆元!"<<endl;  
	}else
		cout<<endl<<"d的逆元为: "<<e.getId()<<endl;
	cout<<endl<<"Press any key to Quit"<<endl;
	getch();

}