互いに素な自然数 a と b について \(a^{-1} \pmod b\) を \(O(\log b)\) で求めるアルゴリズムとして拡張ユークリッドの互除法があるが、今回はその実装を短くするテクニックを紹介する。拡張ユークリッドの互除法の動作原理自体は知っていることを前提とする。

\(ax+by=1\) を満たす \(0 < x < b\) を求めれば \(ax=1 \pmod b\) となり \(a\) の逆元が求まる。\(0 < y=b^{-1} \pmod a< a\)とすれば \(1-by\) は \(a\) で割り切れるから \(x=(1-by)/a\) は \(ax+by=1\) を満たす。あとは \(0 < x < b\) を満たすように \(x\) に \(b\) を足し引きして調節すれば良い。

\(0 < y=b^{-1} \bmod a\ < a\) のとき \(by=1+qa \ ( 0 < q < b )\) と表せて \(0 < b+(1-by)/a < b\) であるから \(x=(1-by)/a+b\) とすれば良い。\(y=b^{-1} \bmod a\) は再帰すれば求まる。

Python のコードにすると次のようになる。

def inv(a, b):
    if a == 1:
        return 1
    else:
        return b + (-b * inv(b % a, a) + 1) // a