Pythonでモジュラ逆数を求める (modinv)

モジュラ逆数（Modular multiplicative inverse）を求めるPythonプログラムについて説明します。 剰余演算 (mod) において逆数 (逆元) を求めるときにモジュラ逆数が出てきます。 モジュラ逆数を求めるアルゴリズムをPythonで書くと次の通りです。 def xgcd(a, b): x0, y0, x1, y1 = 1, 0, 0, 1 while b != 0: q, a, b = a // b, b, a % b x0, x1 = x1, x0 - q * x1 y0, y1 = y1, y0 - q * y1 return a, x0, y0 def modinv(a, m): g, x, y = xgcd(a, m) if g != 1: raise Exception('modular inverse does not exist') else:

[Gln]

“def xgcd(a, b): x0, y0, x1, y1 = 1, 0, 0, 1 while b != 0: q, a, b = a // b, b, a % b x0, x1 = x1, x0 - q * x1 y0, y1 = y1, y0 - q * y1 return a, x0, y0 def modinv(a, m): g, x, y = xgcd(a, m) if g != 1: raise Exception('modular inverse does not exist') else: return x % m”