ユークリッド互除法

2数の最大公約数を求める。

• ユークリッドの互除法

2数 $x,y$ の最大公約数 $gcd(x,y)$ とともに、

$$ ax + by = gcd(x,y) $$

となる $(a,b)$ の組の1つも見つける。

組の1つが見つかれば、後は $u=\frac{x}{gcd(x,y)},v=\frac{y}{gcd(x,y)}$ として

$$ ..., (a-2v,b+2u), (a-v,b+u), (a,b), (a+v,b-u), (a+2v,b-2u), ... $$

が過不足なく全て等式を満たす組となる。

# 引用(もといパクリ)
# Python で RSA 公開鍵暗号をなぞってみる - CAMPHOR- Tech Blog
# https://tech.camph.net/rsa-public-key-encryption/

def ex_euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1

    while c1 != 0:
        m = c0 % c1
        q = c0 // c1

        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)

    return c0, a0, b0

互除法とは直接関係ないが、一緒に使うことがある制約条件について。

• $x,y,z$ から、$ax+by=z$ となる $a,b$ を求める
• ただし $a \ge 0,b \ge 0$
• $a$ をあり得る中で最小にする

$a,b$ が正という条件で全探索する時、$a$ を最小（最大でもいいが）にしておくとやりやすい。

まず、$c=gcd(x,y)$ として、$z$ が $c$ の倍数で無い場合、等式は不可能である。

次に、拡張ユークリッド互除法で $a'x+b'y=c$ となる $a',b'$ を求める。$w=\frac{z}{c}$ とすると、$a'xw+b'yw=cw=z$ となり、$(a,b)=(a'w, b'w)$ が答えの一つとなる。

その後、非負チェックと $a$ の最小化を行う。$a$ は $v=\frac{y}{c}$ 単位でしか増減できないので $a\%v$ が最小値となる。負の場合だが、pythonでは $a$ が負であっても $a\%v$ で正の最小値が求まる。

def exex_euclid(x,y):
    c, a, b = ex_euclid(x, y)
    w, m = divmod(z, c)
    
    # zがcの倍数でないなら等式は不可能
    if m != 0:
        return None
        
    u, v = x // c, y // c
    a, b = a * w, b * w

    # aを非負数の中で最小にする
    f, a = divmod(a, v)
    b += u * f
    
    # aを最小にしたのにbが負なら、ともに正の組は不可能
    if b < 0:
        return None

    return c, a, b, u, v