利用者:Rhat1/sandbox

応用

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

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

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

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

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

例えば、合同方程式

X ≡ 4 (mod 5)

X ≡ 4 (mod 7)

X ≡ 6 (mod 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和の定義で重要な位置を占めている。