반응형
알고리즘/알고리즘 이야기
-
확장 유클리드 호제법 (EEA)알고리즘/알고리즘 이야기 2022. 1. 1. 17:45
유클리드 호제법에서는 최대공약수를 빠르게 찾을 수 있었다. int gcd(int a, int b){ if(b==0) return a; return gcd(b,a%b); } 이 때 나오는 최대공약수를 d라고 하자. gcd(a,b) 의 값이 d이다. 우리는 ax + by = d 가 되는 x와 y를 찾고 싶다. "베주 항등식"에 의하여 ax + by = d를 만족하는 x와 y가 무조건 있다. 유클리드 호제법의 과정을 나열해보자. gcd(a,b) => gcd(b,r2) => gcd(r2,r3) => gcd(r3,r4) ... 이런 과정으로 나아갈 것이다. 이 과정을 수식으로 나열 해보면, a = b * q0 + r2