Programming/C/C++2012. 5. 26. 21:47

확장 유클리드 알고리즘이란?

 

정수 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는 0, 1이다.

s1 = s2
s2 = s
t1 = t2
t2 = t

원리 참조 : http://dragon1307.egloos.com/5106569

 

 그럼 m, n의 값이 144, 28일때 확장 유클리드 알고리즘을 적용해보겠습니다.

 

 

적용하면 am+bn = gcd(m, n)에 맞게 (1)*144 + (-5)*28 = 4 가 성립하는 a, b값이 1, -5라는 것을 구할 수 있습니다.

 

c언어 소스

 

 

 

실행 결과

 

 

Posted by bbolmin

댓글을 달아 주세요

  1. hj

    고맙습니다. 잘 배우고 갑니다.

    2016.01.21 11:32 [ ADDR : EDIT/ DEL : REPLY ]