< 암호학 > 유클리드 호제법

설명

유클리드 알고리즘은 두 정수 사이의 최대공약수를 구하는 방식이다.

 

두 정수 사이의 아래와 같은 특성을 이용한다.

큰 수(a)와 작은 수(b) 사이의 최대 공약수 = 큰 수를 작은 수로 나눈 나머지(a mod b)와 작은 수(b) 사이의 최대 공약수 

 

a,b의 최대공약수를 구하기 위해 

GCD(a,b)를 반복적으로 사용하는데, 

만약 b가 0이라면, a값을 리턴하고

b가 0이 아니라면, Euclid(b, a mod b) 를 재귀호출 (또는 while loop 사용) 한다.

 

앞의 파라미터를 계속 뒤의 파라미터로 나눈 나머지로 줄게 만들면서,

어느 순간 뒤 파라미터가 0 (나머지가 0)이 될 때 그 앞 파라미터가 두 수의 최대공약수이다.

 

3개 정수의 최대공약수를 구할 때는, 두 개씩 먼저 적용하면 된다.

gcd(a,b,c) = gcd ( gcd (a,b) , c)

 

c언어 구현 코드

2개 정수 사이의 GCD

// while loop 사용
int gcd(int a, int b) {
    int temp = 0;  
    while (b != 0) { 
        temp = b;  
        b = a % b;  
        a = temp;  
    }
    return a;  // b가 0이 돼서 while을 탈출한 경우, a가 최대공약수
}

// 재귀호출 사용
int gcd(int a, int b) {
    if (b == 0) {
        return a;  // b가 0이면 a가 최대공약수
    } else {
        return gcd(b, a % b);  // 재귀 호출: gcd(b, a % b)
    }
}

 

3개 정수 사이의 GCD

// 두 정수의 GCD를 구하는 함수 (유클리드 알고리즘 사용)
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

// 세 정수의 GCD를 구하는 함수
int gcd_of_three(int a, int b, int c) {
    int g = gcd(a, b);  // a와 b의 GCD 구하기
    return gcd(g, c);   // a와 b의 GCD와 c의 GCD 구하기
}

 

참고 블로그 : https://olrlobt.tistory.com/44