유클리드 알고리즘, 확장 유클리드 알고리즘

유클리드 알고리즘을 이용한 여러 코드를 짜 봅시다! 

 

유클리드 알고리즘으로 GCD 구하기

GCD 즉, 두 수의 최대 공약수를 구하기 위해서 유클리드 알고리즘을 사용할 수 있습니다

두 수 a, b (a>b) 가 있을 때 a를 b로 나눈 나머지가 0이면 b는 a, b의 GCD이다 라는 알고리즘이 유클리드 알고리즘인데요.

이 때 나머지가 0이 아니면 0이 될 때까지 b와 a%b의 수로 위 과정을 반복해 줍니다.

 

swift 코드로 알아볼게요

func gcd(_ a: Int, _ b: Int) -> Int{
    var a = a, b = b
    
    if a < b {
        swap(&a, &b)
    }
    
    if a == b {
        return a
    } else if b == 0 {
        return a
    } else {
        return gcd(b, a % b)
    }
}

재귀함수를 이용한 코드입니다. 

먼저 a > b 인 상태를 맞춰주기 위해 크기 비교 후 b가 더 크면 swap 해 줍니다.

그 후 a 와 b가 같은 수이면, a(아무거나 상관 ㄴ) b가 0 이면 a (그 전 단계에서 b에 해당) 

그 외의 경우에는 재귀로 b와 a % b 두 수로 반복해 줍니다. 

 

print(gcd(710, 310))
print(gcd(0, 7))
print(gcd(3,4))

위 코드를 실행하면 

 

결과가 잘 나오는 것을 볼 수 있습니다.

두 번째 0, 7의 경우 0은 모든 수의 배수이기 때문에 7이 0의 약수가 되어 GCD = 7 이 됩니다. 

 

확장 유클리드 알고리즘 (Extended Euclidean Algorithm)

확장 유클리드 알고리즘은 나머지 연산의 곱셈의 역원을 구할 때 활용이 됩니다.

여기서 곱셈의 역원이란 어떤 수와 곱하였을 때 곱셈의 항등원이 되도록 하는 수를 말하는데요, 

항등원이란 어떤 연산에서 자기 자신의 수를 되게 하는 수를 말합니다. 곱하였을 때 자기 자신이 되게 하는 수가

곱셈의 항등원이겠죠?! 따라서 a*1 = a 가 되게하는 1이 곱셈의 항등원입니다.

그럼 곱셈의 역원은 a*? = 1 이 되게하는 ? 가 되겠습니다. 일반적으로 이 상황에서는 1/a가 될거에요.

 

따라서 나머지 연산의 곱셈의 역원이란

a*? mod n = 1 이 되는 ?를 말합니다! 이 ?를 구하기 위해 확장 유클리드 알고리즘을 사용할 겁니다.

 

이제 진짜 확장 유클리드 알고리즘에 대해서 알아볼게요.

숫자 a, b (a>b)에 대해 

$$a * x + b * y = GCD(a, b)$$

 

위와 같은 수식을 만족하는 x, y를 구하는 알고리즘을 확장 유클리드 알고리즘이라고 합니다. 

먼저 $$a*x_1 + b*y_1 = r_1 \\ a*x_2 + b*y_2 = r_2 $$ 의 식에서 가장 자명한 해인 

$$ (x_1, y_1, r_1) = (1, 0, a) \\ (x_2, y_2, r_2) = (0, 1, b)$$ 를 시작으로 r2가 0이 될 때까지 작업을 수행해 줍니다. 

 

여기서 작업은 q = r1 / r2로 하여 

$$x_{new} = x_1 - q*x_2 \\ y_{new} = y_1 - q*y_2 \\ r_{new} = r_1 - q*r_2 $$ 을 계속해서 수행해 주는 것을 말합니다. 

아까 말했듯이 r2 == 0 일 때까지만요! 

r2가 0이 아니라면 x1, y1, r1 에는 x2, y2, r2를, x2, y2, r2에는 새로 구한 new 시리즈(?)를 넣어주며 해당 작업을 반복합니다.

사실 이 부분은 코드로 보는 게 더 이해가 쉬울 거에요.

 

r2 가 0 이 되면 (x1, y1, r1)을 반환하며, 이 때 y1이 a * ? mod b = 1 에서의 나머지 연산의 곱셈의 역원이 됩니다.

물론 이 때는 GCD(a. b) = 1 즉, 서로소 일 때만 가능합니다. 만약 두 수가 서로소가 아니라면 곱셈의 역원은 존재하지 않아요. 

 

func extendedEuclid(_ a: Int, _ b: Int) -> (Int, Int, Int){
    if a == b {
        return (1, 0, a)
    } else if b == 0 {
        return (1, 0, a)
    } else {
        var x1 = 1
        var y1 = 0
        var r1 = a
        
        var x2 = 0
        var y2 = 1
        var r2 = b
        
        while r2 != 0 {
            let q = r1 / r2
            
            let xt = x1 - q*x2
            let yt = y1 - q*y2
            let rt = r1 - q*r2
            
            x1 = x2
            y1 = y2
            r1 = r2
            
            x2 = xt
            y2 = yt
            r2 = rt
        }
        
        return (x1, y1, r1)
    }
}

 

 

위 GCD를 구할 때와 마찬가지로 a와 b가 같거나 b가 0인 경우에는 자명해인 (1, 0, a)를 반환합니다. 

그 외의 경우에서는 위에서 설명한 바와 같이 while 문을 이용하여 구해줍니다. 

 

 

유클리드 알고리즘은 정수론이나 보안에서 많이 쓰이는 대표적인 수학 이론이기 때문에 잘 알아두면 좋겠습니다!! 

 

 

참고 자료 

https://www.crocus.co.kr/1232