유클리드 호제법과 확장 유클리드 알고리즘

유클리드 호제법 사용 이유

 

유클리드 호제법은 최대 공약수 (gcd) 를 구하는 알고리즘 중 하나이다.

 

대부분 최대 공약수를 구하기 위해 인수분해를 이용했을테지만, 

 

말도 안 되게 큰 수의 최대공약수는 인수분해로 풀기 어렵기 때문에,

 

유클리드 호제법을 사용한다.

 

 

예를들어, 12345 와 123의 최대 공약수를 구해야 할 때는

 

인수분해보다 유클리드 호제법을 사용할 때 더 빠르게 구할 수 있다.

 

유클리드 호제법은 큰 수들의 최대공약수를 쉽게 구하기 위한 알고리즘이다.

 

 

유클리드 호제법 과정 

 

12345 와 123의 최대 공약수를 유클리드 호제법으로 구하면서 방법을 보여주겠다.

 

 

이런 식으로,  처음에 두 수 12345 , 123 이 주어졌다면 

 

12345를 123을 이용해서 나타내준다. 

 

12345 = 123 * 100 + 45 이런 식으로.

 

 

 

 

 

 

그리고 그 다음은 이런 식으로 123을 45를 이용하여 나타내주면 된다.

 

이 과정을 더하는 수가 0이 될 때까지 반복하면 ..

 

9 = 3 * 3 이 되고, 이 때 3이 최대 공약수가 된다.

 

 

그리고, 이는 결국 12345 와 123의 최대 공약수가 3임을 증명하게 된다. 

 

 

주어진 두 수로 식을 어떻게 전개해나갔는지를 이해하고 기억해둔다면 

 

그리 어렵지 않다. ( = 그러니 노력해봐라 ..)

 

진짜.. 진짜 정 어렵다면 이 방법을 써라. 

 

 

올릴 지 말지 백 번 고민하다가 올린 거라 글씨가 좀 더럽다.. :)

 

 

 

만약 123, 12345 이렇게 주어졌다고 

 

123 = 12345 * .. 이렇게 나타낼 필요는 없다 .

 

이렇게 작은 수를 좌변에 두고 식을 전개한다면,

 

곱하는 수는 1보다 작아지므로 좀 답없어질 테니까.. 

 

(저 식만봐도 알 수 있다. 123 = 12345 * x + y 에서 x, y를 구하기는 싫다..)

 

무조건 큰 수를 죄변에 두고 계산해야 한다. 

 

 

확장 유클리드 알고리즘 

 

 

여기까지 이해했다면, 확장 유클리드 알고리즘은 쉽게 할 수 있다. 

 

확장 유클리드 알고리즘을 이용하면, 

 

두 수의 최대 공약수 뿐 아니라

 

두 수가 왜 곱셈의 역원인지도 알 수 있다.

 

곱셈의 역원을 구하는 것에 큰 도움을 주기 때문에 암호학에서 유용하게 쓸 수 있다.

 

 

곱셈의 역원

 

곱셈의 역원에 대해 먼저 설명을 조금 하겠다. 

 

곱셈의 역원은 모듈로(modulo) m에 대해 정의되는 수이다.

 

예를들어, mod 가 26일 때 3의 역원을 구한다 치면

 

3x ≡ 1 (mod 26) 

 

이런 식으로 나타내는데, 

 

이 때 역원은 9가 될 수 있다. (27 mod 26 = 1이기 때문에)

 

 

아, 모듈로 연산 (mod) 에서는 등호 대신 ≡ 를 이용한다. 

 

이는 a와 b가 모듈로 m에 대해 동일한 나머지를 갖는다는 의미로, 

 

위의 식에서 봤을 때는,

 

27을 26으로 나누었을 때의 나머지와

 

1을 26으로 나누었을 때의 나머지는 같은 걸 볼 수 있다.

 

모듈로 기호는 등호와 다르게, 몫은 다르더라도 나머지만 같으면 된다.

 

 

곱셈 암호를 풀기 위해..

 

 

후에 곱셈 암호를 풀기 위해서는

 

최대 공약수가 c인 두 수 a, b가 주어졌을 때,

 

au + bv = c 를 만족시키는 정수 u값과 v값을 구해야 한다.

 

u와 v 값을 구하기 위해서는

 

먼저, 유클리드 알고리즘을 이용해

 

최대 공약수를 구해줘야 한다. 

 

 

유클리드 알고리즘을 이용했다면, 그 후에는 

 

대입을 이용해 풀 수도 있고, 

 

확장 유클리드 알고리즘을 이용해서도 풀 수 있다.

 

확장 유클리드 알고리즘은 x, y 값을 구하는 방법 중 하나이다.

 

 

예를 들어서 각각의 방법에 대해 설명을 하겠다. 

 

222와 690 이라는 두 수가 주어졌다. 

 

먼저 유클리드 알고리즘으로 최대 공약수를 계산해준다. 

 

 

 

 

혹시 몰라 색으로 다시 표시를 해보았다.. :)

 

보이는 것과 같이 최대 공약수는 6임을 알았다.

 

그리고 이제 이걸 이용해 690 u + 222 v = gcd(최대공약수)  꼴로 만들어 줄 것이다. 

 

우선, 나머지 값을 기준으로 식을 정리해준다. 

 

 

 

나머지 값만 두고, 나머지를 우변으로 이항해주면 다음과 같다. 

 

 

여기까지 왔다면, 두 가지 풀이를 이용해 u와 v 값을 구할 수 있다. 

 

 

 

풀이 1. 대입을 이용해 u와 v 값 구하기

 

 

 

먼저, 최대 공약수가 단독으로 있는 식을 찾아주고,

 

주어진 두 수 이외의 다른 수는 두 수로 이루어진 식으로 대체해준다.

 

 

나는 두 수를 각각 알아보기 쉽게 A, B 로 치환해주었다.

 

숫자를 쓰면 헷갈리기 때문에 이 방법을 추천한다. 

 

 

보이는 그대로, 식을 대입하여 풀어낸 것이다.

 

-9A * 27B = 6 이나오고,

 

A = 690 , B = 222 였으니,

 

-9 * 690 + 27 * 222 = 6 이고 이는 우리가 구하려던 꼴과 같다.

 

따라서,  u는 -9, v는 28 이라는 걸 알 수 있었다. 

 

확장 유클리드 알고리즘을 이용해 u와 v 값 구하기

 

다음은  확장 유클리드 알고리즘을 이용해 구하는 방식이다. 

 

편의를 위해 u는 x로  v는 y로 적었다 .. 

 

 

gcd 에 사용된 두 수와, 나머지 값을 이용할 것이다. 

 

맨 윗 줄은  690x + 222y = 690 을 만족시키는 x값과 y 값을 구하라는 뜻이다.

 

그렇다면 x = 1, y =0 이라는 건 쉽게 알 수 있고,

 

두 번째  690x + 222y = 690  222 에서는 x = 0, y = 1 이라는 걸 알 수 있다.

 

 

하지만  690x + 222y = 24 와  690x + 222y = 6은 구하기 어려워보인다.

 

쉽게 구하는 방법이 있는데! 한 번만 외워두면 유용하니 기억하기 바란다.

 

위에서 쓴 곱하기 값을 끌어온 뒤,

 

부호만 음수로 바꾸어주고 바로 이전 값과 곱해준다.

 

그리고 두 번째 이전 값을 각각 더해주면 된다. 

 

이 경우에 x는 (0*3)+1 이므로 1, y는 (1*-3)+0 이므로 -3이 된다.

 

따라서 x =1, y = -3 일 경우에  690x + 222y = 24 를 만족한다. 

 

그럼 그 아래의 x 값과 y 값도 쉽게 구할 수 있다. 

 

이런 식으로.. x= -9 , y = 28 임을 알 수 있다. 

 

손으로 쓰면서 계산을 하다보면, u와 v가 헷갈릴 수도 있어서

 

x와 y로 설명을 했지만,

 

 

x와 y는 각각 u , v 와 같으니,

 

혹시라도 문제에서 u , v 값을 물어본다 하더라도 너무 당황하진 않아도 된다.

 

 

 

확장 유클리드 알고리즘이 필요한 이유

 

 

대입하는 게 훨씬 쉬워보이지만, 

 

사실 그렇지만도 않다. 

 

690과 222같이 작은 수라면 식이 얼마 나오지 않아 대입을 하는 게 더 빠르지만, 

 

12345 와 123 이 주어졌다면 .. 상당히 힘들 것이다. 

 

 

말만으로는 와닿지 않을 것 같아 한 번 가져와 봤다.

 

이 정도의 대입도 괜찮다면 굳이 말리지는 않겠다.

 

하지만 확장 유클리드 알고리즘을 이용한 방식과, 대입을 이용한 방식 모두 이용해보고

 

차이를 직접 느껴보면 좋을 것 같다. 

 

확장 유클리드 알고리즘 계산기

 

https://www.dcode.fr/extended-gcd

Extended GCD Algorithm Calculator - Online Linear Combination Finder

 

다음은 확장 유클리드 알고리즘을 이용해 계산 해주는 사이트다. 

 

 

우측에 두 수를 적고, 하단의 계산하기를 누르면 좌측에 계산 과정과 정답이 나온다.

 

(맨 아래 값이 정답이다.)

 

 

임의의 두 수를 정해 확장 유클리드 알고리즘을 이용해 값을 구한 뒤, 

 

정답을 확인해보면 도움이 많이 될 것 같아 첨부했다.

 

여러 수를 이용해 확장 유클리드 알고리즘을 직접 해보고, 완벽히 익히길 바란다 :)