[C] <암호수학> 확장 유클리드 알고리즘

확장 유클리드 알고리즘

유클리드 알고리즘이란 두 수의 최대공약수를 구하는 방법이다.

#include <stdio.h>
void main() {
    int a, b;
    int r, r1, r2, q[50] = {0};
    int s[50] = { 1,0 };
    int t[50] = { 0,1 };
    printf("a, b = ? ");
    scanf("%d %d", &a, &b);
    r = a;
    r1 = b;
    int count = 0;
    while (r1 >= 1) {
        q[count+1] = r / r1;
        r2 = r%r1;
        if (count >= 2) {
            s[count] = s[count - 2] - q[count-1]*s[count - 1];
            t[count] = t[count - 2] - q[count-1]*t[count - 1];
        }
        printf("%4d = %4d * %4d + %4d\t", r, q[count+1], r1, r2);
        printf("s= %d        t= %d\n", s[count], t[count]);
        r = r1;
        r1 = r2;
        count++;
    }
    s[count] = s[count - 2] - q[count - 1] * s[count - 1];
    t[count] = t[count - 2] - q[count - 1] * t[count - 1];
    printf("gcd = %d = %d * %d + %d * %d\n", s[count]*a + t[count]*b, s[count], a, t[count], b);
}