유클리드 호제법
큰 수를 작은 수로 깎아냅니다
가로 1071cm, 세로 462cm 인 벽을 똑같은 정사각형 타일로 틈 없이 채우려 합니다. 가장 큰 타일의 한 변은 몇 cm 일까요?
두 수를 소인수분해하려 들면 한참이 걸립니다. 그런데 2300년 전 사람들은 이것을 나눗셈 몇 번으로 끝냈습니다. 무엇을 어디에 나눈 것일까요?
이야기
?
Public domain · 위키미디어 공용
『원론』 일곱째 권 첫머리에 이 방법이 나옵니다. 기원전 300년의 글인데, 오늘 컴퓨터가 돌리는 절차와 한 걸음도 다르지 않습니다. 그래서 이것을 세상에서 가장 오래된 알고리즘이라 부릅니다.
그런데 정작 이 절차가 가장 크게 쓰이는 곳은 옛날 땅 나누기가 아닙니다. 인터넷에서 카드 번호를 감출 때 쓰는 RSA 암호가 이것을 씁니다. 이천삼백 년 전의 나눗셈이 지금 이 순간에도 수없이 돌고 있는 것입니다.
왜 큰 수를 작은 수로 계속 바꿔도 답이 안 변할까요. 두 수를 모두 나누는 수는 그 차이도 반드시 나누기 때문입니다. 21과 15를 나누는 3은 그 차인 6도 나눕니다.
거꾸로도 그렇습니다. 그러니 (21, 15)의 공약수와 (15, 6)의 공약수는 완전히 같은 무리입니다. 수만 작아지고 답은 그대로인 것입니다.
그래서 계속 줄이다가 나머지가 0이 되는 순간, 그때 남은 수가 최대공약수입니다.
그는 이 절차를 「서로 빼기」로 적었습니다. 나눗셈이 아니라 큰 것에서 작은 것을 계속 빼는 방식이었습니다. 나눗셈으로 한꺼번에 줄이는 것은 나중에 다듬어진 것이고, 뼈대는 이천삼백 년 전 그대로입니다.
이천삼백 년 된 알고리즘이 지금도 매 순간 돌아갑니다. 암호 열쇠를 만들 때, 분수를 약분할 때 컴퓨터가 이것을 씁니다.
RSA 암호에서 복호화 열쇠를 구하는 셈이 확장된 유클리드 호제법입니다.
계단 넷 — 같은 사실을 네 깊이로
바둑돌로 나누어 본다
가로 12cm, 세로 8cm인 직사각형 종이에서 가장 큰 정사각형(8×8)을 한 장 잘라내 봅니다. 남는 종이는 4×8이 됩니다.
남은 종이에서 다시 정사각형(4×4)을 자르면 딱 두 장으로 빈틈없이 끝납니다. 마지막에 남은 가장 작은 정사각형의 한 변 4가 바로 두 수의 최대공약수임을 종이를 접고 자르며 눈으로 확인해 보세요.
큰 수에서 작은 수를 빼 보세요
남은 것이 최대공약수입니다. 나누어떨어질 때까지 빼면 됩니다.
수로 되풀이해 구하기
두 수 를 로 나누어 몫 와 나머지 이 남는다면 (), 와 의 최대공약수는 와 나머지 의 최대공약수와 완벽하게 같습니다.
큰 수 대신 훨씬 작은 나머지와의 최대공약수를 계속 구하면 수가 눈 깜짝할 사이에 줄어들어 나머지가 0이 되는 순간의 나누는 수가 바로 최대공약수가 됩니다.
나머지로 바꿔 가 보세요
빼기를 나머지로 바꾸면 훨씬 빨라집니다 — 391 과 299 는 세 걸음이면 끝납니다.
왜 반드시 끝나나·증명
이 나눗셈 과정을 되짚어 올라가는 확장 유클리드 호제법(Extended Euclidean Algorithm)을 사용하면 베주 항등식(Bézout's Identity) 를 만족하는 정수해 를 구할 수 있습니다.
라메(Lamé)의 정리에 따르면 호제법의 나눗셈 단계 수는 작은 수의 자릿수의 5배를 넘지 않으며, 피보나치 수열의 이웃한 두 수일 때 최악의 수행 시간을 가짐이 증명되어 알고리즘 복잡도 이론의 시초가 되었습니다.
몇 걸음이면 끝날까요
가장 오래 걸리는 짝은 이웃한 피보나치 수입니다 — 1597 과 987 을 넣어 보세요.
확장 호제법·베주 항등식
유클리드 호제법은 단순한 계산법을 넘어 정역(Integral Domain)이 유클리드 정역(Euclidean Domain)이자 주 아이디얼 정역(PID) 및 유일 인수분해 정역(UFD)이 되도록 보장하는 대수학의 핵심 기둥입니다.
현대 컴퓨터에서는 다항식의 최대공약수 계산, 유리수 근사(연분수 전개), 그리고 RSA 공개키 암호 알고리즘에서 모듈러 곱셈 역원(Modular Inverse)을 구하는 데 없어서는 안 될 핵심 엔진으로 매초 수억 번씩 실행됩니다.
ax + by = gcd 를 풀어 보세요
이것이 RSA 에서 비밀 열쇠 d 를 찾는 바로 그 셈입니다.
풀어 보기
호제법으로 최대공약수 구하기. 두 수 1071과 462의 최대공약수를 유클리드 호제법으로 구하려 한다.
(1) 1071을 462로 나눈 몫과 나머지를 쓰고, 첫 번째 호제법 등식을 완성하시오.
(2) 나머지가 0이 될 때까지 나눗셈 과정을 끝까지 수행하여 의 값을 구하시오.
(3) 등식 를 만족하는 정수해 를 한 쌍 구하시오.
(2) , , 이므로 최대공약수는 21입니다.
답과 풀이 보기
(1) 몫 2, 나머지 147 —
(2) 나머지가 0 이 될 때까지 이어 갑니다.
마지막으로 0 이 아니었던 나머지가 최대공약수이므로 입니다.
⭐ 세 줄이면 끝납니다. 두 수를 소인수분해하려 들면 훨씬 오래 걸립니다.
(3) 입니다.
위 식을 거꾸로 거슬러 올라갑니다.
를 넣으면
확인 : .
2,300 년 전 유클리드의 방법이 지금도 가장 빠릅니다. 카드로 결제할 때, 문자를 보낼 때, 이 세 줄이 1 초에 수천 번 돌아갑니다. 이보다 나은 방법을 2,300 년 동안 아무도 못 찾았습니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
호제법은 가장 오래되고 가장 오래 쓰인 알고리즘입니다.
- 분수 약분 — 컴퓨터가 분수를 줄일 때 이것을 씁니다
- 암호 — RSA에서 열쇠를 만들 때 확장된 형태를 씁니다
- 직접 해 보기 — 모눈종이에 직사각형을 그리고 정사각형을 잘라 내 보세요
이어지는 장
큰 수를 작은 수로 나눈 나머지로 계속 바꾸어가며 최대공약수를 빠르게 뽑아내는 호제법의 원리는, 나머지의 단서들을 모아 감추어진 수를 한 번에 맞히는 제70장 과 함께 정수론과 암호학의 기초를 단단하게 떠받치는 가장 훌륭한 기둥입니다.
영감을 받은 곳
기원전 300년경 유클리드의 『원론』(Elements) 제7권 명제 1과 2에 수록된 것으로, 두 자연수의 최대공약수를 효율적으로 구해내는 인류 역사상 가장 오래된 알고리즘 중 하나입니다.