モジュラ逆元は、数論と暗号理論における基本的な概念です。ある数に別の数を掛け、与えられた法で剰余を取ると、結果が1になる数のことです。この記事では、Pythonでモジュラ逆元を計算するためのいくつかの効率的なアルゴリズムを調べ、それらの効率性と適用性を比較します。
目次
1. ナイーブな反復アプローチ
この単純なアプローチは、条件を満たすものが見つかるまで、可能な逆数を反復的に調べます。理解しやすい一方で、O(m)の時間計算量のため、大きな法に対しては非常に非効率です。
def modular_inverse_naive(a, m):
"""
ナイーブな反復アプローチを使用してモジュラ逆元を計算します。
Args:
a: 逆元を求める数。
m: 法。
Returns:
a modulo mのモジュラ逆元、存在しない場合はNone。
"""
for x in range(1, m):
if (a * x) % m == 1:
return x
return None
# 使用例
a = 3
m = 11
inverse = modular_inverse_naive(a, m)
print(f" {a} modulo {m} のモジュラ逆元は: {inverse}") # 出力: 4
2. モジュラ累乗（フェルマーの小定理）
法mが素数のとき、フェルマーの小定理は効率的な解を提供します。これは、pで割り切れない任意の整数aに対して、ap-1 ≡ 1 (mod p) と述べています。したがって、逆数はap-2 (mod p)であり、モジュラ累乗を用いて効率的に計算できます。この方法はO(log m)の時間計算量を持ちます。
def modular_exponentiation(base, exp, mod):
res = 1
base %= mod
while exp > 0:
if exp % 2 == 1:
res = (res * base) % mod
exp >>= 1
base = (base * base) % mod
return res
def modular_inverse_fermat(a, p):
if p <= 1:
raise ValueError("pは1より大きい素数でなければなりません")
return modular_exponentiation(a, p - 2, p)
# 使用例（pは素数）
a = 3
p = 11
inverse = modular_inverse_fermat(a, p)
print(f" {a} modulo {p} のモジュラ逆元は: {inverse}") # 出力: 4
3. 拡張ユークリッドアルゴリズム
拡張ユークリッドアルゴリズムは、最も一般的で効率的な方法であり、任意の法に適用できます。これは、2つの数の最大公約数（GCD）を求め、それらの数の線形結合として表現します。GCDが1の場合、モジュラ逆元が存在し、容易に求められます。このアルゴリズムもO(log m)の時間計算量を誇ります。
def extended_gcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = extended_gcd(b % a, a)
return (g, x - (b // a) * y, y)
def modular_inverse_euclidean(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
return None # 逆元は存在しません
else:
return x % m
# 使用例
a = 3
m = 11
inverse = modular_inverse_euclidean(a, m)
print(f" {a} modulo {m} のモジュラ逆元は: {inverse}") # 出力: 4
a = 5
m = 12
inverse = modular_inverse_euclidean(a, m)
print(f" {a} modulo {m} のモジュラ逆元は: {inverse}") # 出力: None
4. 結論
この記事では、モジュラ逆元を計算するための3つのアルゴリズムを紹介しました。ナイーブなアプローチは単純ですが非効率です。フェルマーの小定理は、素数の法に対して効率的な解を提供します。拡張ユークリッドアルゴリズムは、逆元が存在する任意の法に適用できる最も汎用的で効率的な方法であり、特に暗号理論において、ほとんどのアプリケーションで最適な選択肢となります。