유클리드 알고리즘과 확장된 유클리드 알고리즘

안녕하세요 강민성입니다.

오늘은 유클리드 알고리즘과 그 확장에 대해서 알아보도록 하겠습니다.

유클리드 알고리즘이란?

먼저 유클리드 알고리즘이란 유클리드 호제법이라고도 하며 

두 수에 대해서 최대공약수를 구하는 방법입니다.

두 수가 일반적인 방법으로 최대 공약수를 구하기 너무 커졌을 때

이 유클리드 알고리즘을 사용하면 보다 쉽게 구할 수 있습니다.

이제 유클리드 알고리즘을 살펴보면

두 수 a,b에 대해서(a>b),

a = q * b + r  라 하면 q 는 몫, r은 나머지가 됩니다.

이 때,  gcd(a,b) = gcd(b,r) 이 성립하고

이와 같은 과정을 계속 거쳐

나머지가 0이 되었을 때 나누는 수가 a,b의 최대공약수에 만족하게 됩니다.

예시를 통해서 알아볼까요?

240꽈 46의 최대공약수를 구한다고 하겠습니다.

240 = 46 x 5 + 10

46 = 10 x 4 + 6

10 = 6 x 1 + 4

6 = 4 x 1 + 2

4 = 2 x 2 + 0

다음과 같이 반복하다가 나머지가 0이 되었을 때

나누는 수 2가 최대공약수 되는 것입니다.

이를 파이썬 코드로 짜보았습니다.

ef gcd(a,b):
    if a<b: # 큰 수가 앞에 오도록 값 교환
        a,b = b,a
    while b != 0: # 나머지가 0이 될 때
        a,b = b, a% b
    return a # 나눈 수를 return
 
answer = gcd(240,26)
print(answer) # 2
 

위에서 설명한 내용과 주석으로 자세한 설명은 대체 하겠습니다.

그렇다면 이 유클리드 알고리즘을 확장하면 어떻게 될까요?

확장된 유클리드 알고리즘

기존의 유클리드 알고리즘에서 구하고 싶었던 것이 최대공약수 였다면

이번에는 부정방정식의 해 입니다.

어떠한 형태의 부정방정식이내면

gcd(a,b) = a* x + b * y

다음과 같은 형태의 부정방정식입니다.

해석하자면 두 수의 최대공약수를 두 수에 정수곱의 합으로 표현할 수 있다는 의미죠.

위의 예제를 다시 가져와 부정방정식의 해를 구해보도록 하겠습니다.

240 = 46 x 5 + 10 에서

식을 변형해서 10 = 240 X1 + 46 x (-5)  ------------------ (i)

46 = 10 x 4 + 6 에서

식을 변형해서 6 = 46 - 10 x 4

                         = 46 - (i) x 4

  = 46 - 240 x 4 + 46 x 20

  = 240 x (-4) + 46 x 21 -------------------(ii)

10 = 6 x 1 + 4 에서

식을 변형해서 4 = 10 - 6 x 1

  = (i) - (ii) x 1

= 240 x 1 - 46 x 5 - 240 x (-4) - 46 x 21

= 240 x 5 + 46 x (-26) -------------------(iii)

6 = 4 x 1 + 2 에서

식을 변형해서   2 = 6 - 4 x 1

= (ii) - (iii) x 1

= 240 x (-4) + 46 x 21 - 240 x 5 + 46 x (-26)

= 240 x (-9) + 46 x 47 ---------------------------------(iiii)

4 = 2 x 2 + 0 이므로 종료.

즉 240과 46의 최대공약수는 아까와 같이 2이고

2 = 240 * x + 46 * y

을 만족시키는 부정방적식의 해는 x = -9 y = 47 이 됩니다.

위 과정을 프로그래밍에 적용시키기 위해

좀 더 일반화 해보도록 하겠습니다.

r1 = a , r2 = b

s1 = 1 , s2 = 0

t1 = 0 , t2 = 1

을 초기값으로 시작해서

r1 = 240, r2 = 46 이 될 것 입니다.

그리고 이 두 수를 r 과 s,t 로 표현을 해줍니다.

r1 = 240 = s1 x r1 + t1 x r2

r2 = 46 = s1 x r1 + t2 x r2

가 되고 이 식을 이용해서 r s t 를 업데이팅 해줍니다.

q 를 r1 을 r2로 나눈 몫 r을 나머지라고 하면 

r  =  r1 - q x r2

r1 = r2

r2 = r

s = s1 - q x s2

s1 = s2

s2 = s

t = t1 - q x t2

t1 = t2

t2 = t 

이 과정을 반복하여  r2 가 0 이 되었을 때,

gcd(a,b) = r1

x = s1

y = t

가 됩니다.

이를 코드로 작성하면 

def EEA(a,b):
    r1,r2 = a, b
    s1,s2 = 1, 0
    t1,t2 = 0, 1
    
    while(r2>0):
        q = r1 // r2
        r = r1 - q * r2
        r1,r2 = r2,r
 
        s = s1 - q * s2
        s1,s2 = s2,s
 
        t = t1 - q * t2
        t1,t2 = t2,t
 
    print("{} = {}*({}) + {}*({})".format(r1, a,s1,b,t1))
 
EEA(161,28) # 7 = 161*(-1) + 28*(6)

다음과 같습니다.

마무리

지금까지 유클리드 알고리즘에 대해서 알아보았습니다.

생각보다 최대공약수를 이용하는 문제도 많이 나오고

확장된 유클리드 알고리즘 같은 경우에는

암호학에서 요긴하게 쓰인다고 합니다.

기회가 된다면 어디에 어떻게 쓰이는지도 포스팅 해보도록 하겠습니다.

지금 까지 글을 읽어주셔서 감사합니다 :)