モジュラ逆数

テンプレート:Expand English テンプレート:Refimprove 合同算術において、法 テンプレート:Math に関する整数 テンプレート:Mvar のモジュラ逆数（モジュラぎゃくすう、テンプレート:Lang-en-short）とは,

$ax\equiv xa\equiv 1(\mathrm{mod}m)$

という関係にある整数 テンプレート:Mvar の属する合同類（あるいはその標準的な代表元）のことで、これを テンプレート:Math で表す。これは、整数の法 テンプレート:Mvar に関する合同類環 $\mathbb{Z}/m\mathbb{Z}$ における乗法逆元である。ある種の応用においては、モジュラ逆数 テンプレート:Math が $\mathbb{Z}/m\mathbb{Z}$ に属さないような場合を考えることもある。

テンプレート:Mvar の テンプレート:Mvar を法とする逆数が存在するための必要十分条件は テンプレート:Mvar と テンプレート:Mvar とが互いに素（即ち、最大公約数 テンプレート:Math が テンプレート:Math）となることである。法 テンプレート:Mvar に関する テンプレート:Mvar のモジュラ逆数が存在するならば、テンプレート:Mvar を法とした テンプレート:Mvar による除法（「余り付き除法」ではない）を、モジュラ逆数を掛けることとして定義することができる。

例

整数 テンプレート:Math の法 テンプレート:Math に関するモジュラ逆数 テンプレート:Mvar を求める。これは

$3^{-1}\equiv x(\mathrm{mod}11)$

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

$3x\equiv 1(\mathrm{mod}11)$

なる x を求めることに他ならない。$\mathbb{Z}/11\mathbb{Z}$ においてこの合同式の解 テンプレート:Mvar が テンプレート:Math であることは

$3\times 4=12\equiv 1(\mathrm{mod}11)$

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

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

の形をしており、これは テンプレート:Math という集合を成す。

逆数計算

拡張ユークリッド互除法

法 テンプレート:Mvar に関する テンプレート:Mvar のモジュラ逆数は、拡張ユークリッド互除法を用いて計算することができる。互除法のアルゴリズムはベズーの等式

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

の解を求めるものである。ただし、テンプレート:Math が既知で、整数 テンプレート:Math および テンプレート:Math がこのアルゴリズムから求まる。

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

$ax\equiv 1(\mathrm{mod}m)$

の解であったから、合同式の定義により テンプレート:Math（テンプレート:Mvar は テンプレート:Math の約数）、即ち適当な整数 テンプレート:Mvar を用いて

$ax-1=qm$

となる。これを整理した

$ax-qm=1$

は、テンプレート:Mvar と テンプレート:Mvar が既知で、逆数となる テンプレート:Mvar と捨てられる テンプレート:Mvar は未知であるから、拡張ユークリッド互除法が解く等式とまったく同じ形をしている。違う点といえば テンプレート:Math が「求まる」のではなくて「所与」であること程度で、それゆえ テンプレート:Mvar が テンプレート:Mvar と互いに素でなければならず、さもなくば逆元 テンプレート:Mvar は存在しない。

このアルゴリズムの計算量は テンプレート:Math と仮定すると テンプレート:Math で、一般に冪乗の計算よりも効率的である。

オイラーの定理の利用

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

オイラーの定理によれば、テンプレート:Mvar が テンプレート:Mvar と互いに素ならば、オイラー函数 テンプレート:Math に対して

$a^{\phi (m)}\equiv 1(\mathrm{mod}m)$

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

$a^{\phi (m)-1}\equiv a^{-1}(\mathrm{mod}m)$

と求まる。これから、テンプレート:Mvar が素数である特別の場合には、テンプレート:Math ゆえ

$a^{-1}\equiv a^{m-2}(\mathrm{mod}m)$

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

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

応用

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

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

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

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

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

例えば、合同方程式

$X\equiv 4(\mathrm{mod}5)$

$X\equiv 4(\mathrm{mod}7)$

$X\equiv 6(\mathrm{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}(\mathrm{mod}5)=3$

$t_2=(5\times 11{)}^{-1}(\mathrm{mod}7)=6$

$t_3=(5\times 7{)}^{-1}(\mathrm{mod}11)=6$

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

$X\equiv 3504\equiv 39(\mathrm{mod}385)$

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

また、モジュラ逆数はテンプレート:仮リンクの定義で重要な位置を占めている。

関連項目

• 逆数合同法
• 合同算術
• 剰余演算
• 整数の合同
• 初等数論
• 公開鍵暗号
• ユークリッドの互除法