1.6.2. 逆元¶
Code: modular_arithmetic.py
逆元とは¶
Inverse element (Wikipedia)
乗法における逆数のことである。
\[ax \equiv 1 \pmod n\]
であるとき \(x\) を逆元といい、\(a^{-1}\) と表記する。
逆元の求め方¶
拡張ユークリッドの互除法を用いて求められる。まず、逆元の定義から式変形して
\[ax - 1 \equiv 0 \pmod n\]
とする。合同の定義より
\[ax - 1 = kn\]
と表せる整数 \(k\) が存在する。これを式変形して
\[ax - nk = 1\]
とすれば、上式は \(x, k\) に関する一次不定方程式とみなせ、\(\gcd(a, n) = 1\) であれば整数解を持つことがわかる。
実装¶
概要¶
法 \(n\) における \(a\) の逆元 \(a^{-1}\) を求める。
実装のポイント¶
逆元の候補は無数に存在するため、剰余をとって \(0 \leq a^{-1} < n\) を満たすものを返すようにした。
計算量¶
mod_inv(a, n)\(\mathcal{O}(\log{\min(a, n)})\)
コード¶
[1]:
from __future__ import annotations
class InversionError(Exception):
def __init__(self):
self.message = "Inverse element is not defined."
def extgcd(a: int, b: int) -> tuple[int, int, int]:
if b == 0:
return (a, 1, 0) if a > 0 else (0, 0, 0)
p, q = divmod(a, b)
d, x, y = extgcd(b, q)
return (d, y, x - p * y)
def mod_inv(a: int, n: int) -> int:
d, x, y = extgcd(a, n)
if d != 1:
raise InversionError()
return x % n