ps:확장_유클리드_알고리즘
확장 유클리드 알고리즘
유클리드 알고리즘
- 그냥 유클리드 알고리즘(=유클리드 호제법)은, 두 수의 최대공약수를 구하기 위해 사용되는 알고리즘이다.
- 로직도 심플하고 코드도 간단하게 작성 가능하다 (재귀함수로 구현하면 한줄에도 가능).
- 하지만 최대공약수는 math.gcd 함수로 쉽게 구할수 있기 때문에 굳이 작성할 일은 없다.
- 유클리드 알고리즘으로 n과 m의 최대 공약수를 계산하는데에 걸리는 시간 복잡도는 O(log(max(n,m))) 이다
베주 항등식
- 이름은 항등식인데.. 내용은 정리에 가깝다. 내용은
- 두 정수 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)) 이 된다.
확장 유클리드 알고리즘
- m과 n이 주어졌을때, nx+my=gcd(n,m) 을 만족시키는 정수 x0와 y0, 그리고 gcd(n,m)을 함께 구해준다
- 코드는 유클리드 알고리즘을 조금만 수정하면 된다. 시간복잡도도 동일하게 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를 먼저 구하고 역원을 다시 구해야 하므로 속도상으로는 좀 비효율적일수 있지만, 계산 자체가 가벼워서 별로 차이는 안난다. 확장 유클리드 알고리즘을 반복해서 적용해야 하는 문제를 본적도 없어서 별 신경 안써도 될것 같다
- 그것보다는, 그냥 확장 유클리드 알고리즘 코드를 구현해도 워낙 심플하기 때문에 굳이 이렇게 회피해야 하는가 하는 생각은 든다.
ps/확장_유클리드_알고리즘.txt · 마지막으로 수정됨: 2021/08/13 05:53 저자 teferi
토론