モジュラ逆数を求める方法はいくつかありますが、ここでは2つの一般的な方法を紹介します。
-
拡張ユークリッドの互除法 拡張ユークリッドの互除法は、aとmの最大公約数を求める手法です。この手法を使って最大公約数が1であることを確認した後、拡張ユークリッドの互除法を適用することでモジュラ逆数を求めることができます。
def extended_gcd(a, b): if a == 0: return b, 0, 1 gcd, x, y = extended_gcd(b % a, a) return gcd, y - (b // a) * x, x def modular_inverse(a, m): gcd, x, _ = extended_gcd(a, m) if gcd != 1: raise ValueError("Inverse does not exist.") return x % m上記のコードでは、
extended_gcd関数で拡張ユークリッドの互除法を実装し、modular_inverse関数でモジュラ逆数を計算しています。 -
フェルマーの小定理 フェルマーの小定理は、素数pと整数aが互いに素（最大公約数が1）である場合、a^(p-1) ≡ 1 (mod p)が成り立つことを述べています。この定理を応用して、モジュラ逆数を求めることができます。
def modular_inverse(a, m): if math.gcd(a, m) != 1: raise ValueError("Inverse does not exist.") return pow(a, m - 2, m)上記のコードでは、
pow関数を使ってa^(m-2)を計算し、モジュラ逆数を得ています。
これらの方法を使ってモジュラ逆数を計算することができます。モジュラ逆数は、暗号学や数学的な計算においてさまざまな応用があります。