1.6.3. 素数を法とする逆元¶

Code: modular_arithmetic.py

Test: test_modular_arithmetic.py

フェルマーの小定理¶

Fermat’s little theorem (Wikipedia)

法 $p$ が素数ならば、拡張ユークリッドの互除法の代わりに、累乗 (繰り返し二乗法) により逆元を求めることができる。

累乗で逆元を求めるには、フェルマーの小定理

\[a^p \equiv a \mod p\]

を用いる。

逆元 $a^{-1}$ が存在する ($\gcd(p, n) = 1$ を満たす) とき、上式の両辺に $ a^{-1}$ を2回掛けると

\[a^{p-2} \equiv a^{-1}\]

となり、逆元は $a^{p-2}$ で求まることがわかる。

実装¶

概要¶

繰り返し二乗法で冪乗 $a^x \pmod p$ を計算する。指数 $x$ は負数でも良く、 $a^{-1}$ で逆元を求める。

Pythonの組み込み関数 pow で上位機能が既に実装されているが、ここでは素数の法 $p$ かつ $\gcd(a, p) = 1$ の制約下で再実装した。

実装のポイント¶

逆元の存在判定は行わない実装とした。

逆元の存在判定が必要であれば、拡張ユークリッドの互除法を使うほうが良い。

また、指数部の処理にはフェルマーの小定理から得られる関係式

\[a^{x + (p-1)} \equiv a^x \pmod p\]

を用いた。

計算量¶

mod_pow(a, p) $\mathcal{O}(\log{p})$

コード¶

[1]:

def mod_pow(a: int, x: int, p: int) -> int:
    x %= (p-1)
    y = 1
    while x > 0:
        if x & 1 == 1:
            y *= a
            y %= p
        x >>= 1
        a *= a
        a %= p
    return y

使用例¶

[2]:

inv = mod_pow(7, -1, 1000000007)
print(inv)
print(7 * inv % 1000000007 == 1)

142857144
True