モジュラー乗法逆数電卓

モジュラー乗法逆数とは何ですか？

法 m に関する整数 a のモジュラー乗法逆数とは、[0, m-1] の範囲にある整数 x で、以下の式を満たすものです。

これは a⁻¹ (mod m) と書き、通常の算術における乗法逆数（例: 1/a）に似ていますが、モジュラー算術の世界での概念です。

重要な条件: 逆数が存在するのは、gcd(a, m) = 1、つまり a と m が互いに素である場合に限られます。

計算方法: 拡張ユークリッド互除法

最も効率的な方法は拡張ユークリッド互除法を使用することです。これは、ベズーの等式を満たす整数 x と y を見つけます。

gcd(a, m) = 1 のとき、両辺の mod m をとると a·x ≡ 1 (mod m) となり、x がモジュラー逆数となります。

例: 3⁻¹ (mod 7) を求める:

拡張ユークリッド互除法により: 3·(5) + 7·(-2) = 15 − 14 = 1 となり、3⁻¹ ≡ 5 (mod 7) です。検証: 3 × 5 = 15 = 2×7 + 1 ≡ 1 (mod 7) ✓

暗号学と数学における応用

よくある質問