최대 공약수 (GCD; Greatest Common Divisor)

최대 공약수가 뭔지는 생략해도 충분할듯.

최대 공약수 알고리즘

가장 유명한 것은 유클리드 알고리즘이고, 시간복잡도도 O(logn)으로 최적이지만, 실질적으로는 좀더 빠르게 돌아가는 Binary GCD 알고리즘이나 Lehmer's algorithm 등도 있다.
파이썬에서는 math.gcd 함수에 구현되어 있기 때문에, 굳이 직접 구현할 필요는 없다.
- 내부 구현은 Lehmer's algorithm 이라고 한다.

유클리드 알고리즘

Euclidean algorithm (Euclid's algorithm 으로도 불린다)
유클리드 호제법이라고도 불린다.
두 양의 정수의 최대 공약수를 구하기 위해 사용되는 알고리즘. 중학교 수학 교과에도 포함되어 있고, 코딩 과목을 듣다보면 코드로 짜는 연습도 한번쯤은 해보게 된다.
기원전 300년경에 기록되어서, 인류 최초의 알고리즘으로도 알려져있다.
- 원래 알고리즘은 스텝마다 나눗셈을 하는게 아니라, 스텝마다 뺄셈을 하는 방식이었다고 한다.. 이건 좀 느린데;;
로직도 심플하고 코드도 간단하게 작성 가능하다 (재귀함수로 구현하면 한줄에도 가능).
유클리드 알고리즘으로 GCD(n,m)을 구할때 필요한 나눗셈의 횟수는 O(log(max(n,m)))이다.
- PS에서는 나눗셈을 O(1)로 취급하니까 그냥 시간복잡도가 O(log(max(n,m)))이라고 생각하면 간단하다.
- 이것을 제대로 처음 증명한것이 Lamé's Theorem인데, 계산복잡도 이론의 시초라고 한다

Binary GCD algorithm

Binary GCD algorithm
Stein's algorithm 이라고도 불리긴 하지만, 실제로는 스타인이 1967년에 발표하기 훨씬전인 기원전 2세기에 중국에서 이미 알려져 있었다고 한다.
나눗셈을 쓰지 않고, 비트쉬프트연산과 뺄셈만으로 GCD를 구하도록 개선된 알고리즘
시간복잡도는 유클리드 알고리즘과 동일하게 O(log(max(n,m))이지만, 실질적으로는 더 빠르게 돌아간다고 한다.

Lehmer's GCD algorithm

Lehmer's GCD algorithm
큰수들 간의 GCD를 구할때 효율적이다
cpython의 math.gcd는 이 알고리즘으로 구현되어 있다
- Pypy에서는 그냥 유클리드 알고리즘으로 구현되어있기 때문에, 큰수의 GCD를 구할 때에는 pypy가 훨씬 느리다는 이야기가 있다. (https://foss.heptapod.net/pypy/pypy/-/issues/3031)

베주 항등식

Bézout's identity
이름은 항등식인데, 내용은 정리에 가깝다. (Bézout's lemma 라고도 불린다고 한다)
내용은
- 두 정수 n, m 이 있을때, nx+my=gcd(n,m) 을 만족시키는 정수 x와 y가 반드시 존재한다
- 정수 x와 y에 대해서 nx+my=d 를 만족시키는 정수 d는 항상 gcd(n,m)의 배수이다.
여기서 바로 알수 있는 것들은
- nx+my=c 라는 부정방정식이 있을때, c가 gcd(n,m)의 배수가 아니라면 x,y의 정수해가 존재하지 않는다
- (x0, y0)가 nx+my=d 의 하나의 해일때, 일반해는 (x0 + k*m/gcd(n,m), y0 - k*n/gcd(n,m)) 이 된다

확장 유클리드 알고리즘 (Extended Euclid Algorithm)

m과 n이 주어졌을때, nx+my=gcd(n,m) 을 만족시키는 정수 x0와 y0, 그리고 gcd(n,m)을 함께 구하는 알고리즘
- 이런 x,y가 존재한다는 것은 베주 항등식에서 알수 있다.
코드는 유클리드 알고리즘을 조금만 수정하면 된다. 시간복잡도도 동일하게 O(log(max(n,m)))
이제 nx+my=c 의 해를 다음 과정으로 구할 수 있다.
- 확장 유클리드 알고리즘을 통해서 gcd(n,m)과 nx+my=gcd(n,m)를 만족시키는 x0, y0 를 구한다
- c % gcd(n,m) != 0이면 해가 없다. 그렇지 않으면 x0*c/gcd(n,m), y0*c/gcd(n,m) 이 nx+my=c 의 해가 된다
- 일반해는 (x0*c+k*m)/gcd(n,m), (y0*c-k*n)/gcd(n,m) 이 된다
확장 유클리드 알고리즘이 사용되는 가장 흔한 경우는 모듈러 역원을 계산하는 것이다.
- a의 m에 대한 모듈러 역원 x는 a*x % m = 1 을 만족하는 x이다
- 이걸 다시 쓰면 ax-my = 1 이 된다. 즉, gcd(a,m)이 1보다 크면 역원이 없고, 서로소라면 a,m에 대해서 확장 유클리드 알고리즘을 돌리면 x값을 찾을수 있다.
파이썬에는 pow함수가 모듈러 역원을 계산해주기 때문에 모듈러 역원 계산을 위해서 확장 유클리드 알고리즘을 새로 코딩할 필요는 없다. 오히려 역으로 pow함수를 이용해서 확장 유클리드 알고리즘을 구현하는 것도 가능하다.
- nx+my=gcd(n,m)를 만족하는 정수 x0,y0을 찾는다고 하자.
- 먼저 math.gcd를 이용해서 gcd(n,m) = g 를 계산하자
- 양변을 g로 나눠서 (n/g)x + (m/g)y = 1 로 만들고 이항하면, (n/g)*x ≡ 1 mod (m/g) 가 되므로 x=pow(n/g, -1, m/g)로 계산할수 있다. y도 마찬가지로 y=pow(m/g, -1, n/g) 으로 계산하면 된다.
- gcd를 먼저 구하고 역원을 다시 구해야 하므로 속도상으로는 좀 비효율적일수 있지만, 계산 자체가 가벼워서 별로 차이는 안난다. 확장 유클리드 알고리즘을 반복해서 적용해야 하는 문제를 본적도 없어서 별 신경 안써도 될것 같다
- 그것보다는, 그냥 확장 유클리드 알고리즘 코드를 구현해도 워낙 심플하기 때문에 굳이 이렇게 회피해야 하는가 하는 생각은 든다.

목차

최대 공약수 (GCD; Greatest Common Divisor)

최대 공약수 알고리즘

유클리드 알고리즘

Binary GCD algorithm

Lehmer's GCD algorithm

베주 항등식

확장 유클리드 알고리즘 (Extended Euclid Algorithm)