拡張ユークリッドの互除法

拡張ユークリッドの互除法(extended Euclid's algorithm)

ａとｎが互いに素（つまり GCD(ａ, ｎ) = 1) であれば、法ｎに関するａの乗法的逆元（略して逆数とも呼ぶ）が存在する。つまり、

ａ χ ≡ 1 (mod ｎ )

を満足する χ が存在する。この χ を求めるのは不等方程式 ａ χ + ｎｙ = 1 を解く事にほかならず、下に示したアルゴリズムによる解法を拡張ユークリッドの互除法(extended Euclid's algorithm) と呼ぶ。


long
modinv(a, n)
    long            a;
    long            n;
{
    long            q, s, t, u, v, w;

    s = a;
    t = n;
    u = 1;
    v = 0;

    while (s > 0) {
        q = t / s;
        w = t - q * s;
        t = s;
        s = w;
        w = v - q * u;
        v = u;
        u = w;
    }
    return ((v + n) % n);
}