최대공약수 (유클리드 알고리즘을 이용)

gcd(a,b)로 표현 하기도 하는 이번 글에선 최대공약수를 다뤄보려고 한다.

우리가 보통 최대공약수를 구하는 방법음 다음과 같다.

2 │ 48 18
3 │ 24 9
└────
8 3
이렇게 구한 뒤에 세로로 곱한다면 최대공약수가 나오는 방식으로 여태까지 구해 왔다.

하지만 컴퓨터는 이러한 방법으로는 최대공약수를 구하지 못한다.
또한 각 수를 모두 소수로 분해해야 하기에 매우 비효율적이다.

지금부터 컴퓨터가 해결할 수 있도록 위에서 구한 식을 함수 gcd(a,b)를 이용해 풀어보자.

======================================================================

그전에 먼저 mod(모듈러)에 대해 알아야 한다.
mod 계산은 C언어의 %연산자와 같은 역할은 한다. 즉, 나머지를 구하는 연산자라는 것이다.

예를 들어,

105 mod 10 = 5 이다.

또한 mod연산자는 양쪽에 쓰지 않고 한쪽으로 몰 수 있는데,
105 = 15 (mod 10) 이렇게쓰여 있다면,
105 mod 10 = 15 mod 10
5 = 5가 된다.

======================================================================

그럼 이제 다시 최대공약수로 돌아가서 함수 gcd(a,b)에 대해 알아보자.

함수 gcd(a,b)의 작동 방식은 gcd(a,b) = gcd(b,a mod b)로 매우 단순하다.
예를 들어, a=48, b=18 이라면,

gcd(48,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) 이 된다.
그리고 b=0이므로 gcd(48,18) = gcd(6,0)= 6 이다.
즉, b자리가 0이되면 최대공약수는 a인 것이다.

자 이제 알고리즘을 만들어 보자 (유클리드 알고리즘)

1. gcd(a,b)에서 b값이 0이 아니라면, a mod b 연산을 실행
2. a 자리에 b를 넣고 a mod b의 결과를 b의 자리에 넣는다.
3. 1,2를 반복한다. 만약 b=0이라면 a값이 최대공약수이다.

알고리즘은 mod 만 안다면 매우 간단하다.
이제 알고리즘을 C로 코딩해보자.

#include <stdio.h>
#include <stdlib.h>
#define INT unsigned int 

INT gcd(INT a, INT b) {
	if (0 == b) return a;
	return gcd(b, a % b);
}

끝이다. 정말 이게 끝이다.
솔직히 이런 방법은 생각치도 못했었다. 하지만 누가 2줄로 완성했다는 소리를 듣고 어떻게 짜야 2줄 이내로 짤 수 있을까 고민 하던 중

“반환 값을 함수로 주면 되겠다.” 라는 생각에 실제로 해보니 결과는 성공적이였다. ~~여기서 한 수 알아갔다.~~

이로써 최대공약수와 소수를 찾을 수 있게 되었다.

이제 N=p×q, $\varphi$ (N) = (p-1)(q-1)와 유클리드 호제법만 만들면 RSA를 만들기 위한 기본적인 함수 준비는 모두 끝나게 된다.

[제 4강] 최대공약수.function