モジュラ逆数 (modular multiplicative inverse)
概要
ある \(a\), \(m\) について \(ax \equiv 1\) (mod \(m\)) となる \(x\) を求める。
逆数 \(x\) が存在するための必要十分条件は \(\gcd(a, m) = 1\) を満たすことである。
拡張ユークリッドの互除法による計算
\(ax + my = \gcd(a, m) = 1\) の \(x, y\) の解を拡張ユークリッドの互除法で計算する。
この \(x\) が \(ax \equiv 1\) (mod \(m\)) を満たす。
累乗による計算
オイラーの \(\varphi\) 関数 \(\varphi(m)\) に対し、オイラーの定理より \(a^{\varphi(m)} \equiv 1\) (mod \(m\)) を満たすため、 \(x \equiv a^{\varphi(m)-1}\) を計算することで求まる。
\(\varphi(m)\) の前計算が必要であるが、 \(m\) が素数であれば \(\varphi(m) = m-1\) であるため、 \(x \equiv a^{m-2}\) を計算することで求まる。
実装
# Extended Euclidean Algorithm
def extgcd(a, b):
if b:
d, y, x = extgcd(b, a % b)
y -= (a // b)*x
return d, x, y
return a, 1, 0
# find the value of x s.t. ax ≡ 1 (mod m)
# by using extended Euclidean algorithm
def inverse(a, m):
d, x, _ = extgcd(a, m)
if d != 1:
# no inverse exists
return -1
return x % m
# Euler's totient function
def euler_phi(n):
res = n
x = 2
while x*x <= n:
if n % x == 0:
res = res // x * (x-1)
while n % x == 0:
n //= x
x += 1
if n > 1:
res = res // n * (n-1)
return res
# find the value of x s.t. ax ≡ 1 (mod m)
# by using Euler's theorem
def inverse(a, m):
# φ(m) = m-1 if m is a prime
phi = euler_phi(m)
res = pow(a, phi-1, m)
if res*a % m != 1:
# no inverse exists
return -1
return res