확장 유클리드 호제법
이전에 유클리드 호제법에 대해 알아본 적이 있었습니다. 유클리드 호제법과 확장 유클리드 호제법 모두 정수론을 이용한 알고리즘인데요, 유클리드 호제법이 a와 b의 최대 공약수 gcd(a, b)를 구하는 알고리즘이었다면, 확장 유클리드 호제법은 더 나아가 a와 b의 최대 공약수 gcd(a, b)와 ax+by = gcd(a, b)를 만족하는 x, y까지 구하는 알고리즘 입니다. 그럼 확장 유클리드 호제법을 어떻게 사용하는지 알아보겠습니다. 확장 유클리드 호제법을 사용하기 위해 간단한 규칙을 먼저 살펴봐야 합니다. 아래 규칙을 통해서 Ri가 0이 될 때까지 반복했을 때 마지막으로 나온 Xi, Yi가 gcd(a, b)를 만족하는 x, y가 됩니다. 초기 설정해줘야 하는 값은 X0 = 1, X1 = 0, Y0 = ..
2021. 3. 25.
