암호 관련 수학 공부 | 확장유클리드 알고리즘 | Extended Euclidean Algorithm

유클리드 호제법

두 개의 자연수리 최대공약수를 "빠르게" 구하는 알고리즘.

여기서 빠르게 라는 말은 인간이 빠르게 구하려고 하는것도 물론 맞지만 컴퓨터가 빠르게 계산하기 위함인 것도 있다.

a와 b를 나눈 나머지를 r이라고 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

아 티스토리에서 라텍스 쓰는법 모르겠어요~~~

 

a % b = r이면 gcd(a, b) = gcd(b, r) (단, b > r > 0)

36 % 24 = 12 이고,

24 % 12 = 0 이므로, 0이 되기 한 단계 전인 12가 36과 24의 최대공약수임.

이걸 코드로 표현해보면,

#include <stdio.h>

int GCD(int a, int b)

{

    if (a % b == 0)

        return (b);

    return GCD(b, a % b);

}

int main(void)

{

    printf("%d\n", GCD(36, 24));

}

이렇게 C언어로 재귀적인 표현이 가능하다.

얍. 그냥 이렇다는 사실 정도만 알고 넘어가도록 하자.

다음 글에서 확장 유클리드 호제법을 공부해보도록 하자.