EED(Extend Euclid Algorithm)[c]

1. 확장 유클리드 알고리즘

∀a,b ∈Z, If gcd(a,b)=d, then ∃x,y ∈Z s.t ax+by=d

: 유클리드 알고리즘을 이용해 두 수의 최대공약수를 구하는 거라면 확장 유클리드 알고리즘은 거꾸로 수행하며 x,y를 찾는 과정이라고 할 수 있다

: 이 점을 이용하여 두 개의 정수가 서로소, 즉 gcd의 값이 1일 땐 하나의 수에 대한 다른 수의 곱셈에 대한 역원을 계산할 수 있다

: gcd(a,n)=1 (a<n) <=> ax+ny =1

                              <=> (ax+ny)(mod n) = 1(mod n)

                              <=> ax(mod n) + ny(mod n) =1(mod n) (모듈러 연산의 덧셈성질)

                              <=> ax(mod n) = 1 (mod n)

                              <=> ax =1 (mod n)

-> 단항식의 해를 구하는 과정은 n을 법으로 하는 a의 곱셈의 역원을 구하는 것과 동일해진다

 

(1) EED 동작 

: ∀a,b ∈Z(a≥b), sxa + txb = gcd(a,b) 만족하는 gcd와 s,t 값 도출

이때 a= b*q+r (division algorithm)

1) Division Algorithm 

: ∀a,b ∈Z, b>0 then ∃! q, r s.t a= b*q +r(0≤r<b) 

(2) EED 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int EED(int mod, int x) {
	//mod값을 법으로 하는 x의 역원을 구할 것임
	int r1 = mod;
	int r2 = x;
	int r;
	int quotient;
	int s1 = 0;
	int s2 = 1;
	int s;
	while (r2 != 0) {
		quotient = r1 / r2;
		r = r1 - (r2 * quotient);
		s = s1 - (s2 * quotient);
		s1 = s2;
		s2 = s;
		r1 = r2;
		r2 = r;
	}
	return s1;
}

int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}
int main() {
	int a, b;
	printf("두 수를 입력하시오 : ");
	scanf("%d%d", &a, &b);

	if (gcd(a, b) != 1) {
		printf("역원을 구할 수 없습니다\n");
		return;
	}
	else {
		if (a < b) {
			int res = EED(b, a);
			res += b;
			printf("%d를 법으로 하는 %d의 곱셈의 역원 :%d", b, a, res);
		}
		else {
			int res = EED(a, b);
			if (res < 0) {
				res += a;
			}
			printf("%d를 법으로 하는 %d의 곱셈의 역원 :%d", a, b, res);
		}
	}

	
	getchar();
	return 0;
}