1. gcd

int gcd(int a, int b)
{
    int tmp;
    while(b != 0) {
        tmp = a % b; // 값 갱신을 위해 임시 저장을 함
        a = b; // 기존 b를 a로
        b = tmp; // b에는 a%b를 한 값으로 대체하며 값을 줄여나감.
    }
    return a;
}

gcd(a, b) = gcd(b, a mod b)を繰り返しながら数字を減らしていく。

tmp 変数に aと b の残りを一時的に保存し、既存 b を a に移した後、 b に tmp 値を入れた。

このように繰り返し、b==0であれば繰り返しを終え、aを最大公約数にreturnした。

2. xgcd

int xgcd(int a, int b, int *x, int *y)
{
    int d0 = a, d1 = b;
    int x0 = 1, y0 = 0, x1 = 0, y1 = 1;
    int q, d;
    int x2, y2;

    while (1) {
        q = d0 / d1;
        d = d0 - q*d1;

        if (d == 0) {
						// d == 0일 때 반복을 끝내고 값을 할당
            *x = x2; 
            *y = y2;
            return d1; 
        }
        
        x2 = x0 - q*x1;
        y2 = y0 - q*y1;

				// 값을 갱신함
        d0 = d1;
        d1 = d;
        x0 = x1;
        x1 = x2;
        y0 = y1;
        y1 = y2;
    }
}

Extended Euclidean Algorithm によって、gcd (a, b) = gcd (b, a%b) = gcd (d, 0) = d = ax + byであるが、ここでx, y 値を割り出す。

q を通じて元を求めた後、di+1 = di-1 - qidi を通じてwhile文を繰り返し、di+1 値が0になるまで探す。

なぜなら、di+1 値が0 であるということは、gcd(a、b) = di = axi + byi であり、ここでdi が最大公約数であるからである。

そのようにdi+1の値が0になると、探そうとしたx、yに値を割り当て、diの役割であるd1をreturnする。

d1, d2, d3...., x1,x2,x3.... このようにすると、やりにくくなるので、新しくwhile文が回る前に値を更新してくれる。

3. mul_inv

int mul_inv(int a, int m)
{
    int d0 = a, d1 = m;
    int x0 = 1, x1 = 0, q;
    int tmp;

    while (d1 > 1) { // d가 1이 될때까지 반복
        q = d0 / d1;

        d0 = d0 - q * d1;

        tmp = d0;
        d0 = d1;
        d1 = tmp;

        x0 = x0 - q * x1;

        tmp = x0;
        x0 = x1;
        x1 = tmp;
    }
    if (d1 == 1)
        return (x1 > 0 ? x1 : x1 + m); // x1이 음수이면 m을 더해서 양수로 바꿔 return.
    else 
        return 0;
}

上のxgcdとは違って、ここではy値を使っていないが、modulomに対する逆数なのでxk値だけを求めるだけで良いからである。

Extended Euclidean Algorithm と同様にwhile文を繰り返しながら値を求め、d1 == 1 になると逆が存在するという意味でxk をreturnするが、ここで条件付き三項演算子を利用してx1 値が負数ならx1 +mをする。

なぜなら、モジュラー演算で負の数を使わずに陽の数に変わることがあるからこのようにする。 (m を足すのは、モジュラー演算において何ら意味がないからである)

4. umul_inv