モジュラ逆数

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

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

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

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

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

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 を求めることに他ならない。Z/11Z においてこの合同式の解 x が 4 mod 11 であることは

$3 (4) = 12 \equiv 1 \pmod{11}$

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

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

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

逆数計算

拡張ユークリッド互除法

法 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)²) で、一般に冪乗の計算よりも効率的である。

オイラーの定理の利用

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

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

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

が成り立つ。これは a が法 m に関する既約合同類群 (Z/mZ)^× に入るための必要十分条件が 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 での除法を行う標準的なバイナリ法は利用できるが、m が大きければ遅くなる。さらに言えば、任意の種類の冪剰余は計算量 O(log φ(m)) = O(log m) の重い演算になる。

関連項目

• 逆数合同法
• 合同算術
• 初等数論
• 公開鍵暗号