先に感想
題名の通り、剰余類の逆元演算について結合法則が成り立つというもの。よく考えれば当たり前のように見えるが個人的にはとても非自明で驚きだったのでブログにした。
定理
剰余類 \(Z_n \) の逆元が存在する任意の元 \( a, b \) について以下の等式が成立する。
$$ (ab)^{-1} = a^{-1} b^{-1} $$
証明
\( n \) が素数の場合、フェルマーの小定理から直感的に導くことができる。
参考: フェルマーの小定理 ja.wikipedia.org
フェルマーの小定理より、 \( Z_n \) のある元 \( a \) の逆元 \( a^{-1} \) は以下のように求まる*1。
$$ a^{-1} = a^{n-2} $$
これを用いると \(( Z_n \) の2つの元 \(a, b\) の積の逆元は以下のように書き下せる。
$$ (ab)^{-1} = (ab)^{n-2} = a^{n-2} b^{n-2} = a^{-1} b^{-1} $$
これを一般の \( n \) について拡張する。
オイラーの定理より、\( Z_n \) の元 \( a \) の逆元は(存在するならば)以下の計算で求まる。
$$ a^{-1} = a^{\phi (n) - 1} $$
ところで、逆元が存在することと \( \lbrace a, a^2, \cdots, a^{\phi (n)} \rbrace \) が巡回群であることは同値であることが知られている。既約剰余類群の存在条件と性質より。
参考1: 第8章 既約剰余類群
https://pc1.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2013/08.pdf
このことから、法 \( n \) において \( \phi (n) - 1 \neq 2 \phi (n) - 1 \neq \cdots \) である一方、巡回群なので \( a^{\phi (n) - 1} = a^{2 \phi (n) - 1} = \cdots \) であることが分かる。法 \( n \) における \( a \) の逆元が全て同じであることが確認できたので、後は素数の場合と同じ議論で定理を導くことができる。
何に使える
これによって本質的な計算量削減が実現することはないが、法 \( n \) について 「\( \prod_{x=a}^{p} x\) を \( a \leq p \leq b\) について全て求めたい」というような場合に剰余演算の回数を減らすことができる。剰余演算は非常に重い処理なので、回数を減らすことで大きく計算時間を短縮することができる場面が存在する。
実用例: mod p で 1からnまでの階乗を全て求める
以下のような検証コードを書いて検証した。
from Crypto.Util.number import getPrime import time P = getPrime(1024) bound = 50000 print('case: (x!)^-1') start = time.time() result = [] x = 1 result.append(x) for num in range(2, bound): x *= num x %= P result.append(pow(x, -1, P)) end = time.time() print(f'query time: {end - start} sec') print('case: (x^-1)!') start = time.time() result2 = [] x = 1 result2.append(x) for num in range(2, bound): x *= pow(num, -1, P) x %= P result2.append(x) end = time.time() print(f'query time: {end - start} sec') print('---validate---') assert result == result2 print('validate complete')
結果は以下のようになった。
> python3 rap.py case: (x!)^-1 query time: 9.657723188400269 sec case: (x^-1)! query time: 0.4380009174346924 sec ---validate--- validate complete
計算時間の大きな改善が確認でき、かつ実験的に定理が正しいことも確かめられた。
