유클리드보다 빠른 GCD? 비트 연산으로 풀어내는 이진 GCD 알고리즘

왜 다시 GCD 이야기를 하냐면요

최대공약수(GCD) 구하는 알고리즘, 다들 유클리드 알고리즘 쓰실 거예요. 코딩 테스트 단골이고, 학교에서도 제일 먼저 배우죠. 그런데 이게 사실 최선이 아니라는 걸 아시나요? 현대 CPU 환경에서는 유클리드보다 훨씬 빠른 이진 GCD(Binary GCD) 알고리즘이 있거든요. 1967년 요제프 슈타인(Josef Stein)이 제안한 건데, 그래서 슈타인 알고리즘이라고도 불려요.

이 이야기가 왜 의미 있냐면, 암호학·블록체인·저수준 시스템 프로그래밍에서 GCD 연산은 꽤 자주 등장하거든요. 큰 정수 연산에서 1%의 속도 차이가 누적되면 엄청난 차이가 나는 분야들이에요.

이진 GCD는 어떻게 동작하나요

이게 뭐냐면, 나눗셈 대신 뺄셈과 비트 시프트(2로 나누기)만 쓰는 알고리즘이에요. 원리는 세 가지 성질을 이용해요.

첫째, 두 수가 모두 짝수면 공약수에서 2를 빼놓고 생각할 수 있어요. 예를 들어 gcd(12, 18)은 둘 다 2의 배수니까 2 × gcd(6, 9)와 같죠. 둘째, 한쪽만 짝수라면 그 수에서 2를 나눠도 공약수는 변하지 않아요. gcd(6, 9)에서 6은 짝수, 9는 홀수니까 gcd(3, 9)로 줄일 수 있어요. 9가 홀수니까 2가 공약수일 수 없거든요. 셋째, 둘 다 홀수면 큰 수에서 작은 수를 빼도 공약수는 유지돼요. gcd(3, 9) = gcd(3, 6)처럼요.

이 세 가지를 반복하면서 숫자를 줄여나가는데, 핵심은 나머지 연산(%)이 한 번도 나오지 않는다는 거예요. 2로 나누는 건 단순히 오른쪽 시프트 한 번(>>1)이고, 홀짝 판별도 비트 AND 한 번이면 끝이니까요.

왜 더 빠른가

유클리드 알고리즘의 발목을 잡는 건 사실 나눗셈 연산이에요. 현대 CPU에서 나눗셈은 덧셈이나 시프트보다 10~40배 느린 연산이거든요. x86 64비트 DIV 명령어는 20~80 사이클 걸리는데 SHIFT는 1 사이클이면 끝나요. 어마어마한 차이죠.

또 하나 재밌는 최적화가 있어요. '두 수를 몇 번이나 2로 나눌 수 있는지' 세는 연산이 반복되는데, 이건 CPU 내장 명령어 __builtin_ctz(count trailing zeros)로 한 번에 구해요. 2진수 끝에 붙은 0의 개수를 세는 건데, 이게 곧 2로 몇 번 나눌 수 있는지와 같거든요. 40은 101000이라 끝에 0이 3개, 즉 8로 나눠진다는 뜻이죠. 이 최적화까지 적용하면 표준 라이브러리 GCD보다 2~3배 빠른 성능을 낼 수 있어요. 실제로 GCC의 std::gcd도 내부적으로 이진 GCD 기반이에요.

업계에서는 어떻게 쓰이나

이진 GCD는 특히 다정도 정수(bignum) 라이브러리에서 핵심이에요. GMP, OpenSSL의 BN 모듈, 비트코인의 libsecp256k1 같은 암호학 라이브러리 내부에 다 들어가 있어요. RSA 키 생성이나 타원곡선 연산에서 수천 비트짜리 정수의 GCD를 구할 때 이 속도 차이는 무시할 수 없거든요.

최근엔 Lehmer's GCD, 확장 이진 GCD(모듈러 역원 계산용) 같은 파생 알고리즘도 활발해요. 블록체인 영지식 증명(ZKP) 쪽에서는 GCD 연산이 제약(constraint) 수를 크게 차지해서, 회로 최적화 관점에서도 이진 버전을 선호해요.

한국 개발자가 알아두면 좋은 점

실무에서 직접 구현할 일은 많지 않아요. 솔직히 std::gcd, math.gcd 쓰면 되거든요. 하지만 '왜 이 방법이 더 빠른가'를 이해하는 건 가치가 커요. CPU 친화적 코드가 어떤 건지, 나눗셈을 피하는 게 왜 중요한지 감을 잡을 수 있거든요.

특히 PS·경쟁 프로그래밍 하시는 분들, 아니면 저수준 최적화가 필요한 임베디드·그래픽스·게임 엔진 쪽 계신 분들은 한 번쯤 직접 구현해보시면 비트 연산 감각이 확 늘어요. 확장 유클리드 대신 확장 이진 GCD도 같은 맥락에서 익혀두면 모듈러 역원 구현할 때 든든해요.