モジュラ逆数 (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