モジュラ逆数とは？意味をやさしく解説

モジュラ逆数とは

合同算術において、法 m > 1 に関する整数 a のモジュラ逆数（modular multiplicative inverse）とは、以下の合同式を満たす整数 x のことです。

math
ax \equiv xa \equiv 1 \pmod{m}

この x は a^-1 と表記され、合同類環 \(\mathbb{Z}/m\mathbb{Z}\) における乗法逆元となります。

モジュラ逆数の存在条件

整数 a の法 m に関するモジュラ逆数が存在するための必要十分条件は、a と m が互いに素であること、つまり最大公約数 gcd(a, m) が 1 であることです。

モジュラ逆数の意味

モジュラ逆数が存在する場合、法 m における a による除算は、モジュラ逆数を掛ける操作として定義できます。これは、通常の除算とは異なり、割り切れない場合でも定義できる強力な概念です。

モジュラ逆数の例

整数 3 の法 11 に関するモジュラ逆数 x を求める例を考えます。これは、

math
3x \equiv 1 \pmod{11}

を満たす x を求めることに相当します。この例では、x = 4 が解となり、

math
3 \times 4 = 12 \equiv 1 \pmod{11}

となることが確認できます。したがって、法 11 における 3 のモジュラ逆数は 4 となります。この合同式を満たす解は 4 のみではなく、4 + 11z（z は整数）の形をした集合 {…, -18, -7, 4, 15, 26, …} に属するすべての整数が解となります。

モジュラ逆数の計算方法

モジュラ逆数の計算には、主に以下の二つの方法が用いられます。

拡張ユークリッド互除法

拡張ユークリッド互除法は、以下のベズーの等式を満たす整数 x, y を求めるアルゴリズムです。

math
ax + by = \gcd(a, b)

モジュラ逆数の計算においては、合同式

math
ax \equiv 1 \pmod{m}

の解を求めることになります。これは、適当な整数 q を用いて

math
ax - 1 = qm

と変形できます。さらに、

math
ax - qm = 1

となり、拡張ユークリッド互除法で解くべき等式と同一の形式になります。ただし、この場合 \(\gcd(a, m) = 1\) は所与の条件となります。拡張ユークリッド互除法は、\(|a| < m\) の場合、計算量が \(O((\log m)^2)\) となり、一般に冪乗計算よりも効率的です。

オイラーの定理の利用

オイラーの定理を用いることでもモジュラ逆数を計算できます。オイラーの定理によれば、a と m が互いに素であるとき、オイラー関数 \(\varphi(m)\) に対して、

math
a^{\varphi(m)} \equiv 1 \pmod{m}

が成り立ちます。したがって、モジュラ逆数は直接的に

math
a^{\varphi(m)-1} \equiv a^{-1} \pmod{m}

として求めることができます。特に、m が素数の場合には \(\varphi(m) = m - 1\) であるため、

math
a^{-1} \equiv a^{m-2} \pmod{m}

となります。この方法は、拡張ユークリッド互除法に比べて一般に計算速度は劣りますが、冪乗剰余の実装が利用できる場合には有用です。

ただし、オイラーの定理を用いる際には、

\(\varphi(m)\) を計算するために m の素因数分解が必要となる。
冪乗計算のコストが高い（モンゴメリ法を用いることで効率化できる場合がある）。

などの点に注意が必要です。

モジュラ逆数の応用

モジュラ逆数は、様々なアルゴリズムで重要な役割を果たしています。

RSA暗号

RSA暗号では、暗号化と復号にモジュラ逆数が用いられます。具体的には、2つの大きな素数から生成される鍵ペアのうち、一方が公開鍵として暗号化に用いられ、もう一方が秘密鍵として復号に用いられます。この鍵の生成にモジュラ逆数が利用されています。

高速な除算処理

ワードサイズ（通常32bit）の整数を要素にもつリストを、奇数でkの倍数である整数kで割る場合、

math
k^{-1} \pmod{2^w}

を事前に計算しておき、リストの各要素に掛けて下位wビットを取り出すことで、除算よりも高速な計算が可能となります。

中国剰余定理

中国剰余定理を用いて、複数の合同式を満たす解を求める際にもモジュラ逆数が使われます。例えば、

math
X \equiv 4 \pmod{5}
X \equiv 4 \pmod{7}
X \equiv 6 \pmod{11}

のような連立合同式の解は、モジュラ逆数を用いて計算できます。この例の場合、X ≡ 39 (mod 385) が解となります。

その他

モジュラ逆数は、Kloosterman和の定義にも用いられるなど、数論における様々な場面で重要な役割を果たしています。

まとめ

モジュラ逆数は、合同算術における除算の概念を拡張する重要な概念です。拡張ユークリッド互除法やオイラーの定理などのアルゴリズムを用いることで効率的に計算でき、RSA暗号、高速な除算処理、中国剰余定理など、様々な分野で応用されています。

参考文献

(参考文献は省略)

もう一度検索

モジュラ逆数