// inverse.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

int euclid(int f,int d)
{   //calclate gcd(f,d),note gcd(f,d)=gcd(|f|,|d|)
	//assume f is larger then d
	
	int x=0;  
	int y=0;
	int r=0;
    
	//give the value of argc to the local variable
	if(f<0)
		x=-f;
	else 
		x=f;
	if(d<0)
		y=-d;
	else
		y=d;
	
	if(y==0)  //if divisor is zero 
		return x;
	
	r=x;
    while(y>0)
	{
		r=y;
		y=x%y;
		x=r;
	}
	return r;
}

int ex_euclid(int n,int e)
{	//caculate the inverse of e in Zn
	//f>d>0
	int q=0; //temp variable
	
	//define 3 struct:X,Y,T
	struct Str_X{
		int X1;
		int X2;
		int X3;
	}X;

	struct Str_Y{
		int Y1;
		int Y2;
		int Y3;
	}Y;
	struct Str_T{
		int T1;
		int T2;
		int T3;
	}T;

	//initiate the local variable
	X.X1=1;
	X.X2=0;
	X.X3=n;
    
	Y.Y1=0;
	Y.Y2=1;
	Y.Y3=e;
    
	// the inverse of 1 is 1
    if(Y.Y3==1)
		return Y.Y2;
	//end if
	do{
		q=X.X3/Y.Y3;
		T.T1=X.X1-q*Y.Y1;
		T.T2=X.X2-q*Y.Y2;
		T.T3=X.X3-q*Y.Y3;
		
		X.X1=Y.Y1;
		X.X2=Y.Y2;
		X.X3=Y.Y3;
		
		Y.Y1=T.T1;
		Y.Y2=T.T2;
		Y.Y3=T.T3;
	}while(Y.Y3>1);

	if (Y.Y2<0)
		Y.Y2=Y.Y2+n;

	return Y.Y2;
}
int main(int argc, char* argv[])
{
	int n=0; //n is modul
	int e=0; // n>e
    int inverse;
	int gcd;

	do{//to ensure n is a positive integer
		printf("請輸入模數：\n");
		scanf("%d",&n);
		if (n<=0)
			printf("輸入的模數應該是個正整數！\r\n");
	}while(n<=0);

	do{//to ensure e is one of Zn
		printf("請輸入Z%d中的一個元素：\r\n",n);
		scanf("%d",&e);
		gcd=euclid(n,e);
		if(e<=0||e>=n||gcd!=1)
			printf("輸入的元素應該是Z%d中且與%d互素的數！\r\n",n,n);
	}while(e<=0||e>=n||gcd!=1);

	inverse=ex_euclid(n,e);	

	printf("The inverse of %d is %d \r\n",e,inverse);
	return 0;
}