c언어 - 확장 유클리드 알고리즘
확장 유클리드 알고리즘이란? 정수 m, n의 최대 공약를 gcd(m, n)으로 나타낼 때 1. 확장된 유클리드 호제법을 이용하여, am + bn = gcd(m,n)의 해가 되는 정수 a, b 짝을 찾아낼 수 있다. 2. 특히, m, n이 서로소(gcd(m,n) = 1)인 경우 유용한데, 그럼 위의 식은 am + bn = 1이 되고, 여기서 a는 모듈러 연산의 곱의 역원(modular multiplicative inverse)이 되기 때문이다. 등식 : s*m + t*n = gcd(m, n) r = r1-q*r2 --> r1 = q*r2 + r //초기 r1, r2는 (m, n)이고 q는 몫 r은 나머지 s = s1-q*s2 //초기 s1, s2는 1, 0이다. t = t1-q*t2 //초기 t1, t2는..
2012. 5. 26.