Skip to content →

拡張ユークリッド互除法の簡潔な実装

互いに素な自然数 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
短くなってビックリ! 拡張ユークリッドの互除法は再帰・非再帰どちらでも変数が多くなってしまうのが不満だったのですが、この方法であれば楽ですね。

Published in アルゴリズム

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA