Pythonで合同式の逆元を求める

RSAをおさらいしていたら、合同式の逆元を求める必要がありました。合同式の逆元は拡張ユークリッドの互除法を使うと求められるのですが、逆元を求める際にどう拡張ユークリッドの互除法を使えば良いのか解らなくて、手間取ったのでメモしておきます。コードはPythonです。

一応解きたい式を書いておくと以下になります。
[tex]\mathfrak{a}x \equiv 1\ \pmod{\mathfrak{m}}[/tex]

まず拡張ユークリッドの互除法をWikipedia通りに書きます。Wikipediaの擬似コードは何故かgcdの値を返してなかったのでgcdも返すように変更しました。

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

次にこのegcdを使って合同式の逆元を求める訳ですが、どうにも解りやすい説明が見つからなくて困りました。色々見て回った結果、ここでもWikipediaの「Modular multiplicative inverse」が一番解りやすかったです。ページに書かれている通りegcdを使って逆元を求めます。

# ax ≡ 1 (mod m)
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

上記のmodinvで冒頭の式中のxを求められました。結果だけ見るとなんでもないですね。アルゴリズムが苦手なのでもっと精進します。

アルゴリズム系はWikipediaが便利すぎますね。そしてPythonはWikipediaに張られている擬似コードがほぼ機械的な修正のみで動くので素晴らしいです。

Leave a Reply

Your email address will not be published. Required fields are marked *