유클리드 호제법

편집 역사 토론
수치해석 소프트웨어 마지막 수정: 2026-08-23 04:38:52

1. 개요[편집]

유클리드 호제법(Euclidean algorithm)은 두 정수의 최대공약수를 “큰 수를 작은 수로 나눈 나머지로 갈아치우기”를 반복해 구하는 알고리즘으로, 다음 한 줄이 전부다.

gcd⁡(a,b)=gcd⁡(b, a mod b),gcd⁡(a,0)=a\gcd(a,b) = \gcd(b,\ a \bmod b), \qquad \gcd(a,0) = a

나머지는 매 단계 엄격히 줄어들고 음수가 될 수 없으므로 유한 번에 0에 도달하며, 그 직전 값이 답이다. 유클리드의 원론 7권 명제 1~2에 실려 있으니 기원전 3세기부터 지금까지 한 글자도 안 바뀐 채 현역인 알고리즘이고, 실제로 “인류가 가진 가장 오래된 비자명한 알고리즘”으로 흔히 꼽힌다.1

이름의 “호제”(互除)는 서로 나눈다는 뜻이다. 그런데 이 단순한 절차의 사정거리가 의외로 길다 — 모듈러 역원, 연분수, 다항식 인수분해, 컴퓨터 대수 시스템의 유리수 산술, 심지어 원주율의 새 공식을 찾아내는 정수 관계 탐지까지 전부 이 재귀 한 줄의 후손이다.

2. 뺄셈 버전과 나눗셈 버전[편집]

원론의 원래 형태는 나눗셈이 아니라 반복 뺄셈(그리스어로 안튀파이레시스)이다. 큰 쪽에서 작은 쪽을 계속 빼고, 크기가 뒤집히면 역할을 바꾼다.

while a != b:  if a > b: a -= b  else: b -= a

수학적으로는 같은 알고리즘이지만 복잡도가 다르다. gcd⁡(109,1)\gcd(10^9, 1) 을 뺄셈으로 하면 10억 번을 돌아야 하고, 나눗셈으로 하면 한 번에 끝난다. 즉 나눗셈 버전은 “같은 수를 반복해서 빼는 구간”을 몫 한 번으로 건너뛰는 가속이다.

그럼에도 뺄셈 버전이 죽지 않은 이유가 있다. 나눗셈은 하드웨어에서 가장 비싼 정수 연산이라, 큰 수에서는 나눗셈을 아예 없앤 이진 GCD(Stein, 1967)가 더 빠른 경우가 많다. 짝수/홀수 판정과 시프트, 뺄셈만으로 돌아간다.

  • 둘 다 짝수면 2를 뽑아내고 각각 오른쪽 시프트.
  • 한쪽만 짝수면 그쪽만 시프트(2는 공약수가 아니므로 버려도 된다).
  • 둘 다 홀수면 큰 쪽에서 작은 쪽을 뺀다. 차는 반드시 짝수다.

원론이 “뺄셈만으로도 된다”고 알려 준 사실이 2000년 뒤에 나눗셈기가 느린 하드웨어에서 되살아난 셈이다.2

3. 라메 정리 — 최악은 피보나치[편집]

몇 번 돌면 끝나는가. 라메(Lamé, 1844) 가 답했고, 이것이 역사상 최초의 실용적 알고리즘 복잡도 분석으로 꼽힌다.

a>b>0a>b>0 에 유클리드 호제법을 적용할 때 나눗셈 횟수는 bb 의 십진 자릿수의 5배를 넘지 않는다.

증명의 뼈대는 최악의 입력이 연속한 피보나치 수라는 관찰이다. 나눗셈 횟수를 최대로 만들려면 나머지가 최대한 천천히 줄어야 하고, 그러려면 몫이 전부 1이어야 한다. 몫이 전부 1인 수열이 정확히 피보나치 점화식 Fk+1=Fk+Fk−1F_{k+1}=F_k+F_{k-1} 이다.

gcd⁡(Fn+2,Fn+1) ⇒ 나눗셈 n 회\gcd(F_{n+2}, F_{n+1}) \ \Rightarrow\ \text{나눗셈 } n \text{ 회}

Fn∼φn/5F_n\sim\varphi^n/\sqrt5 이고 log⁡10φ≈0.2090\log_{10}\varphi\approx0.2090 이라 자릿수당 대략 1/0.209≈4.7851/0.209\approx4.785 회 — 여기서 “5배”가 나온다. 즉 호제법의 반복 횟수는 입력 크기의 로그이고, 상수까지 황금비가 잡고 있다.

평균은 더 좋다. 하일브론과 딕슨의 결과에 따르면 나눗셈 횟수의 평균은

12ln⁡2π2ln⁡b≈0.843 ln⁡b\frac{12\ln 2}{\pi^2}\ln b \approx 0.843\,\ln b

로, 최악의 절반 남짓이다. 비트 복잡도까지 따지면 교과서 나눗셈으로 O(log⁡alog⁡b)O(\log a\log b) 이고, 다중정밀에서는 상위 워드만 보고 여러 단계를 한꺼번에 처리하는 레머(Lehmer, 1938)의 기법이, 초대형에서는 분할정복 half-GCD가 O(M(n)log⁡n)O(M(n)\log n) 을 준다.

4. 확장 유클리드와 베주 항등식[편집]

호제법이 진짜 밥벌이를 하는 것은 최대공약수 자체보다 베주 항등식(Bézout’s identity)의 계수를 뱉을 때다.

ax+by=gcd⁡(a,b)ax + by = \gcd(a,b)

확장 유클리드 호제법은 나머지를 갈아치울 때 (x,y)(x,y) 도 같이 끌고 간다. rk=rk−2−qkrk−1r_k = r_{k-2} - q_k r_{k-1} 이라는 나머지 점화식과 똑같은 점화식을 계수에도 먹이면 된다.

xk=xk−2−qkxk−1,yk=yk−2−qkyk−1x_k = x_{k-2} - q_k x_{k-1}, \qquad y_k = y_{k-2} - q_k y_{k-1}

초기값 (x−1,y−1)=(1,0)(x_{-1},y_{-1})=(1,0), (x0,y0)=(0,1)(x_0,y_0)=(0,1). 얻은 계수의 크기는 대략 ∣x∣≤b/(2g)\lvert x\rvert \le b/(2g), ∣y∣≤a/(2g)\lvert y\rvert\le a/(2g) 로 유계라, 중간 값이 폭발하지 않는다는 것도 이 알고리즘의 미덕이다.

가장 많이 쓰이는 결과가 모듈러 역원이다. gcd⁡(a,m)=1\gcd(a,m)=1 이면 ax+my=1ax+my=1 에서 ax≡1(modm)ax\equiv1\pmod m 이므로 xx 가 aa 의 역원이다. 이 한 줄이 떠받치는 것들:

  • 유한체 Fp\mathbb{F}_p 와 Fpn\mathbb{F}_{p^n} 의 나눗셈 — 오류정정부호와 암호의 산술 전부.
  • 공개키 암호의 키 생성. RSA의 개인키 dd 는 ed≡1(modϕ(n))ed\equiv1\pmod{\phi(n)} 를 확장 유클리드로 푼 것이다.
  • 중국인의 나머지 정리의 재구성 계수. 컴퓨터 대수 시스템이 큰 정수 계산을 여러 소수 모듈로 쪼개 병렬로 돌린 뒤 합칠 때 쓴다.
  • 유리수 복원(rational reconstruction). 모듈러 결과를 원래 유리수로 되돌릴 때, 확장 유클리드를 중간에 끊어 r/xr/x 를 읽는다.

5. 연분수와 같은 물건[편집]

몫의 수열 q1,q2,…,qnq_1,q_2,\ldots,q_n 을 그대로 나열하면 그것이 a/ba/b 의 연분수 전개다.

ab=q1+1q2+1q3+⋯\frac{a}{b} = q_1 + \cfrac{1}{q_2 + \cfrac{1}{q_3+\cdots}}

두 알고리즘은 같은 계산의 서로 다른 표기다. 그래서 앞 절의 “최악은 몫이 전부 1”은 연분수 쪽에서 ”[1;1,1,…][1;1,1,\ldots] 가 황금비”라는 사실과 같은 문장이고, 확장 유클리드의 계수 (xk,yk)(x_k,y_k) 는 부호를 빼면 연분수의 수렴분수 분자·분모다. 항등식 pkqk−1−pk−1qk=(−1)k−1p_kq_{k-1}-p_{k-1}q_k=(-1)^{k-1} 이 곧 베주 항등식.

역사적으로 더 흥미로운 것은 원론 10권 쪽이다. 유클리드는 같은 절차를 정수가 아니라 길이에 적용했고, 정사각형의 변과 대각선처럼 절차가 끝나지 않는 쌍이 존재함을 보였다. 끝나지 않는다 = 공약이 없다 = 무리수다. 2=[1;2,2,2,…]\sqrt2=[1;2,2,2,\ldots] 가 무한 연분수인 것이 정확히 그 이야기다. 호제법의 종료 조건이 무리수의 정의였던 셈.

6. 다항식 GCD와 종결식[편집]

체 FF 위의 다항식환 F[x]F[x] 도 나눗셈 정리가 성립하는 유클리드 정역이므로 호제법이 그대로 돈다. 나머지의 차수가 매 단계 줄어드니 deg⁡f\deg f 번 안에 끝난다. 쓰임새는 많다 — 중근 판정(gcd⁡(f,f′)\gcd(f,f') 이 상수가 아니면 중근 있음), 유리함수 약분(전달함수의 극-영점 상쇄), 스텀 수열의 실근 개수 세기가 전부 호제법 위에 있다.

정수·유리수 계수에서는 함정이 있다. 나눗셈을 유리수로 하면 계수의 분자·분모가 지수적으로 부푼다. deg⁡10\deg 10 짜리 두 다항식의 나머지 수열에서 수백 자리 유리수가 나오는 것이 예사다. 그래서 실제 컴퓨터 대수 시스템은 유사나눗셈(pseudo-division)에 부분종결식 나머지 수열(subresultant PRS, Collins 1967 · Brown 1971)을 얹어 매 단계 나오는 공통인자를 정확히 나눠 없애거나, 아예 여러 소수 모듈로 계산하고 중국인의 나머지 정리로 되돌리는 모듈러 GCD를 쓴다.

여기서 종결식(resultant)이 등장한다. f,gf,g 의 종결식은 실베스터 행렬의 행렬식이자 근들의 차의 곱이다.

Res⁡(f,g)=adeg⁡g∏ig(αi),αi=f 의 근\operatorname{Res}(f,g) = a^{\deg g}\prod_{i} g(\alpha_i), \qquad \alpha_i = f \text{ 의 근}

Res⁡(f,g)=0\operatorname{Res}(f,g)=0 인 것과 두 다항식이 공통근을 갖는 것이 동치이므로, 종결식은 “GCD가 상수인가”를 나눗셈 없이 행렬식 하나로 판정한다. 호제법의 나머지 수열과 종결식은 부분종결식 정리로 정확히 연결되어 있고 — 나머지 수열의 원소들이 알려진 인자를 빼면 부분종결식 그 자체다 — 그래서 둘은 사실상 같은 정보의 두 표현이다. 응용은 변수 소거다. 두 곡면의 교선을 구하거나 매개변수 곡면을 음함수로 바꾸는 CAD·CAGD의 음함수화, 판별식 Res⁡(f,f′)/an\operatorname{Res}(f,f')/a_n 계산이 이 도구를 쓴다.

7. 근사 GCD — 부동소수점에서는 성립하지 않는 질문[편집]

여기서부터가 수치해석의 영역이고, 결론은 불편하다. GCD는 불연속 함수다. 공통근을 가진 두 다항식의 계수를 10−1610^{-16} 만 흔들면 공통근이 사라져 GCD가 즉시 1이 된다. 즉 계수가 측정값이거나 부동소수점 연산으로 반올림된 순간, “GCD를 구하라”는 문제는 답이 언제나 1인 무의미한 문제로 바뀐다.

그래서 문제 자체를 다시 쓴다. 근사 GCD(approximate GCD)는 이렇게 묻는다 — 주어진 허용오차 ε\varepsilon 안에서 계수를 흔들었을 때, 차수가 가장 높은 공통인자를 만들 수 있는가? 이건 GCD 계산이 아니라 최근접 특이 문제이고, 도구도 완전히 바뀐다.

  • 실베스터 행렬의 수치적 계수(numerical rank)를 특이값 분해로 읽는다. 계수 결손 dd 가 곧 근사 GCD의 차수 추정이며, 이 접근은 콜리스·잔니·트래거·와트(1995)가 정착시켰다.
  • 차수를 정한 뒤 계수를 최적화하는 구조적 최소자승(STLN 계열)으로 마무리한다.
  • 호제법의 나머지 수열을 그대로 부동소수점으로 돌리는 것은 하지 않는다. 상위 항의 상쇄가 반복 누적되어 남은 유효숫자가 없어진다 — 나머지 수열은 본질적으로 소거이고, 소거는 조건수를 곱으로 키운다.

정리하면 이렇다. 호제법은 정확 산술의 알고리즘이다. 정수·유한체·기호 계산에서는 무적이고, 부동소수점에서는 문제 정의부터 다시 해야 한다. 이 경계선을 못 넘어서 “GCD 코드가 왜 항상 1을 뱉죠?”라는 질문이 매년 반복된다.3

8. PSLQ — 유클리드를 nn 차원으로[편집]

호제법을 두 수가 아니라 nn 개의 실수 x1,…,xnx_1,\ldots,x_n 에 대해 하면 어떻게 될까. 즉

c1x1+c2x2+⋯+cnxn=0,ci∈Z (모두 0은 아님)c_1x_1 + c_2x_2 + \cdots + c_nx_n = 0, \qquad c_i \in \mathbb{Z} \ (\text{모두 0은 아님})

인 정수 관계를 찾는 문제다. n=2n=2 면 x1/x2x_1/x_2 가 유리수인지 묻는 것이고 답은 호제법이다. n≥3n\ge3 으로 올리는 시도는 오일러·야코비 이래 200년간 이어졌지만 신뢰할 만한 알고리즘은 20세기 후반에야 나왔다. 격자 축약(LLL, 1982) 계열과 함께 표준이 된 것이 PSLQ(Ferguson–Bailey, 1992)다. 이름은 부분 제곱합(Partial Sum of squares)과 LQ 분해에서 왔고, 벡터를 직교 여공간에 사영하며 정수 행렬로 축약해 나가는 구조라 호제법의 직교화 버전이라 부를 만하다.

정확도 요구가 가혹하다. 크기 10d10^d 인 계수를 가진 nn 항 관계를 찾으려면 대략 n⋅dn\cdot d 자리의 고정밀 산술이 필요하다 — 혼합 정밀도가 정밀도를 깎아 속도를 사는 세계라면, PSLQ는 정반대로 수백 자리를 사서 정리를 사는 세계다. 그 대가로 얻은 대표적 전리품이 1995년 발견된 원주율의 BBP 공식이다.

π=∑k=0∞116k(48k+1−28k+4−18k+5−18k+6)\pi = \sum_{k=0}^{\infty}\frac{1}{16^{k}}\left(\frac{4}{8k+1}-\frac{2}{8k+4}-\frac{1}{8k+5}-\frac{1}{8k+6}\right)

앞자리를 모르고도 π\pi 의 임의의 16진 자리를 뽑아내는 이 공식은 사람이 유도한 것이 아니라 PSLQ가 수치적으로 찾아내고 사람이 나중에 증명한 것이다. 정수 관계 탐지가 2000년 선정 “20세기의 10대 알고리즘”에 유클리드의 후예로 이름을 올린 이유가 이것.4

9. 관련 문서[편집]

10. Footnotes[편집]

  1. 이 타이틀을 놓고 이집트식 곱셈이나 바빌로니아 제곱근법과 경쟁이 붙곤 하는데, “명시적으로 종료 조건과 반복 구조를 갖춘 절차”라는 기준으로는 대체로 호제법의 손을 들어 준다. 2300년 된 코드가 리팩터링 한 번 없이 표준 라이브러리에 들어 있다는 사실은, 좋은 추상화의 수명에 대해 뭔가를 말해 준다. ↩

  2. 크누스는 이진 GCD의 아이디어가 중국 고대 문헌에 이미 있었다고 적었다. 슈타인이 1967년에 “재발견”한 것인데, 정작 그 시절 컴퓨터에서 나눗셈이 시프트보다 압도적으로 느렸기 때문에 실용적 가치가 생긴 것이다. 요즘 CPU는 나눗셈기가 많이 빨라져서 다시 접전이다. 알고리즘의 우열이 하드웨어 세대마다 뒤집히는, 벤치마크 없이는 아무 말도 하면 안 되는 대표적 사례. ↩

  3. 이 좌절에는 유서 깊은 반론이 따라붙는다 — “그럼 허용오차를 크게 주면 되잖아요?” 문제는 허용오차를 키우면 차수가 낮은 근사 공통인자가 무더기로 생겨 답이 유일하지 않게 된다는 것이다. 근사 GCD는 그래서 언제나 “차수 대 잔차”의 트레이드오프 곡선으로 답하지, 숫자 하나로 답하지 않는다. 특이값 분해의 특이값 그래프에서 “절벽”을 눈으로 찾는 작업이 실제로 벌어진다. ↩

  4. 그 목록에는 몬테카를로 방법의 메트로폴리스 알고리즘, 심플렉스법, 크리로프 부분공간법, QR 알고리즘, 퀵소트, 고속 푸리에 변환, 고속 다중극자법 같은 이름들이 함께 올라 있다. 그 틈에 기원전에 나온 알고리즘의 직계 후손이 끼어 있다는 것이 이 목록의 가장 재미있는 대목이다. ↩