モジュラ逆数

合同算術におけるモジュラ逆数（モジュラぎゃくすう、英: modular multiplicative inverse）は、与えられた整数 $a$ と法 $m$ に関して

a^{-1}\equiv x{\pmod {m}}

という関係にある整数 $x$ の属する合同類（あるいはその標準的な代表元）をいう。即ち、整数の法 $m$ に関する合同類環 $\mathbb {Z} /m\mathbb {Z}$ における乗法逆元である。この式は

ax\equiv aa^{-1}\equiv 1{\pmod {m}}

と書いても同じである。ある種の応用においては、モジュラ逆数 $x$ が $\mathbb {Z} /m\mathbb {Z}$ に属さないような場合を考えることもある。

$a$ の $m$ を法とする逆数が存在するための必要十分条件は $a$ と $m$ とが互いに素（即ち、最大公約数 $gcd(a, m)$ が $1$ ）となることである。法 $m$ に関する $a$ のモジュラ逆数が存在するならば、 $m$ を法とした $a$ による除法（「余り付き除法」ではない）を、モジュラ逆数を掛けることとして定義することができる。

例

整数 $3$ の法 $11$ に関するモジュラ逆数 $x$ を求める。これは

3^{-1}\equiv x{\pmod {11}}

を満たすものを計算するということだが、その意味は

3x\equiv 1{\pmod {11}}

なる x を求めることに他ならない。 $\mathbb {Z} /11\mathbb {Z}$ においてこの合同式の解 $x$ が $4 mod 11$ であることは

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

から明らかであり、従って $11$ を法として $3$ の逆数は $4$ である。こうして $\mathbb {Z} /11\mathbb {Z}$ において逆数が求まったが、上記の合同式を満たす $x$ は $4$ のみではない。残りの解は、得られた $4$ に $m =11$ の倍数を加えたものとして得られる。一般にこの例において $x$ となり得る整数は

4+11z,z\in \mathbb {Z}

の形をしており、これは ${\dots, -18, -7, 4, 15, 26, \dots}$ という集合を成す。

逆数計算

拡張ユークリッド互除法

法 $m$ に関する $a$ のモジュラ逆数は、(拡張ユークリッド互除法)を用いて計算することができる。互除法のアルゴリズムはベズーの等式

ax+by=\gcd(a,b)

の解を求めるものである。ただし、 $a, b$ が既知で、整数 $x, y$ および $gcd(a, b)$ がこのアルゴリズムから求まる。

さて、モジュラ逆数は合同式

ax\equiv 1{\pmod {m}}

の解であったから、合同式の定義により $m | ax - 1$ （ $m$ は $ax - 1$ の約数）、即ち適当な整数 $q$ を用いて

ax-1=qm

となる。これを整理した

ax-qm=1

は、 $a$ と $m$ が既知で、逆数となる $x$ と捨てられる $q$ は未知であるから、拡張ユークリッド互除法が解く等式とまったく同じ形をしている。違う点といえば $gcd(a, m) = 1$ が「求まる」のではなくて「所与」であること程度で、それゆえ $a$ が $m$ と互いに素でなければならず、さもなくば逆元 $x$ は存在しない。

このアルゴリズムの計算量は $| a | < m$ と仮定すると $O ((log m) 2)$ で、一般に冪乗の計算よりも効率的である。

オイラーの定理の利用

拡張ユークリッド互除法の代わりにオイラーの定理をモジュラ逆数の計算に利用することもできる^[1]。

オイラーの定理によれば、 $a$ が $m$ と互いに素ならば、オイラー函数 $φ (m)$ に対して

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

が成り立つ。これは $a$ が法 $m$ に関する(既約合同類群) $(\mathbb {Z} /m\mathbb {Z} )^{\times }$ に入るための必要十分条件が $a$ が $m$ と互いに素であることから従う。従って、モジュラ逆数が直接的に

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

と求まる。これから、 $m$ が素数である特別の場合には、 $φ (m) = m - 1$ ゆえ

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

となる。この方法は一般には拡張ユークリッド互除法よりも遅いが、冪剰余の実装が使える場合には利用されることがある。この方法が不利な点としては、

$φ (m)$ を知るために $m$ の効率的な素因数分解ができなければならないが、一般には素因数分解は困難である（いくつかの自明な例を除く：例えば $m$ が素数あるいは素数冪の場合）
冪乗の計算コスト。冪剰余を用いてより効率的に実装できるが、 $m$ の値が大きいときにはモンゴメリ法を用いるのが最も効率的である。モンゴメリ法自体が、そもそも目的であった法 $m$ でのモジュラ逆数を用いている。モンゴメリ法を用いない場合、冪乗の計算に標準的な(バイナリ法)を用いると、各ステップで法 $m$ での除法を行う必要があるため、 $m$ が大きくなるほど遅くなる。

応用

モジュラ逆数を見つけるという操作は、モジュラ計算を使ったアルゴリズムに多く応用されている。例えば、暗号技術ではモジュラ演算を用いることで、演算をより早く、より少ない記憶容量で行う部分と、演算がより困難な部分がある。^[2]これら二つの性質は共に利点として利用できる。特にRSA暗号では、暗号化・復号には適切に選ばれたモジュラ逆数となる2つの数が使われる。2つのうち1つは公開し、暗号化するために使用される。もう1つは安全に保管しておき、復号に使用する。ここまでの処理は高速だが、1つ目の公開鍵から2つ目の秘密鍵を作るには非現実的な計算コストは避けられないと考えられており、このことがRSA暗号の仕組みを支えている。^[3]

ほかの変わった例を一つ挙げる。ワードのサイズの、kの倍数で奇数である整数を要素に持つ（長い）リストがあったとする。ここで、これらの数をすべてkで割りたい。実装の一つとして次のようなものがある。

$k^{-1}{\pmod {2^{w}}}$ を(拡張ユークリッド互除法)を用いて計算する（wはワードのbit数、通常32）。 $\gcd(2^{w},k)=1$ であるから、これは必ず存在する。
リストの各要素に $k^{-1}$ を掛け、下位 w bit に相当する部分を取り出す（つまり $2^{w}$ で割った余りをとる）。

除算をハードウェアで実装していない処理系にとって、除算は掛け算に比べて遅く、この方法によって格段に処理速度を速めることができる。手順1.には時間はかかるが1回で済むため、扱うリストのサイズが大きければそれだけ効率的である。

このほかモジュラ逆数を用いて、中国の剰余定理によって存在が保証されている合同方程式の解を求めることができる。

例えば、合同方程式

X\equiv 4{\pmod {5}}

X\equiv 4{\pmod {7}}

X\equiv 6{\pmod {11}}

は 5, 7, 11 が互いに素であり解をもつ。解は

X=t_{1}(7\times 11)\times 4+t_{2}(5\times 11)\times 4+t_{3}(5\times 7)\times 6

であり

t_{1}=(7\times 11)^{-1}{\pmod {5}}=3

t_{2}=(5\times 11)^{-1}{\pmod {7}}=6

t_{3}=(5\times 7)^{-1}{\pmod {11}}=6

である。上記の合同方程式を満たしていることは容易にわかる。よって

X\equiv 3504\equiv 39{\pmod {385}}

385 は 5, 7, 11 の最小公倍数である。

また、モジュラ逆数は(Kloosterman和)（英語版）の定義で重要な位置を占めている。

参考文献

^ Koshy, Thomas (2007-05-22). Elementary number theory with applications (2nd ed.). Academic Press. p. 346. ISBN (978-0-12-372487-8)
^ Trappe & Washington 2006, p. 167
^ Trappe & Washington 2006, p. 165

[1] Koshy, Thomas (2007-05-22). Elementary number theory with applications (2nd ed.). Academic Press. p. 346. ISBN (978-0-12-372487-8)

[:0-2] Trappe & Washington 2006, p. 167

[:1-3] Trappe & Washington 2006, p. 165

[1]

[2]

[3]

ウィキペディア	ランダム
毎日	カテゴリ