## 定義 合同算術(modular arithmetic)は、Gauss が *Disquisitiones Arithmeticae* の冒頭で導入した合同(congruence)の概念を出発点とする。a が b と法 n について合同である(a ≡ b (mod n))とは、n | (a − b) が成り立つことをいい、これは rem(a, n) = rem(b, n)(a, b を n で割った余りが等しい)と同値である。合同は反射性・対称性・推移性を満たす同値関係であり、加算・乗算の両方について保存される(a ≡ b かつ c ≡ d ならば a + c ≡ b + d、ac ≡ bd、いずれも mod n)。この保存性により、区間 [0, n) の整数に、加算・乗算をそれぞれ n で割った余りを取る演算 ⊕n・⊗n を入れた**環 Zn**(the ring of integers modulo n)を構成でき、Zn では通常の整数と同じ結合法則・分配法則・交換法則が成り立つ可換環になる。ただし通常の整数や有理数と異なる点として、Zn では乗法逆元(x⁻¹·x = 1 を満たす x⁻¹)が常に存在するとは限らない。k ∈ [0, n) が Zn で乗法逆元を持つのは、k が n と**互いに素**(gcd(k, n) = 1、relatively prime または coprime)であるとき、かつそのときに限り、しかも逆元は存在すれば一意である。この逆元は拡張互除法(Pulverizer)で sn + tk = 1 を満たす s, t を求め、rem(t, n) を取ることで構成的に得られる。さらに、gcd(k, n) = 1 であること、k が Zn で逆元を持つこと、k が Zn でキャンセル可能(ka = kb ⟹ a = b in Zn)であることの3条件は同値になる。この枠組みの上に、Euler の φ 関数 φ(n)(区間 [0, n) 内で n と互いに素な整数の個数、素数 p では φ(p) = p − 1、相異なる素数の積では φ(pq) = (p − 1)(q − 1))と、**Euler の定理**(n と k が互いに素ならば k^φ(n) ≡ 1 (mod n))が定義・証明される。Euler の定理の証明は、Zn* = {k ∈ (0, n) | gcd(k, n) = 1} が乗算で閉じており、任意の k ∈ Zn* による写像 s ↦ k·s が Zn* から Zn* への全単射になることを使い、Zn* の全要素の積を2通りに数えることで導かれる。Fermat の小定理(p が素数で k が p の倍数でなければ k^(p−1) ≡ 1 (mod p))は Euler の定理の特別な場合に当たる。合同算術は、通常の整数演算では巨大になりすぎる数を扱う際に「加算・乗算のたびに余りを取る」ことで計算量を抑える実用的な手段(remainder arithmetic の一般原理)であると同時に、RSA 公開鍵暗号方式の数学的正当性(暗号化・復号の往復が元のメッセージに戻ることの証明)を支える基盤理論でもある。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]], ch.8 §8.6〜§8.10) ## 横断的知見 - **[[公開鍵暗号方式]] concept が集約する RSA の実務的側面(OAEP・PKCS パディング、副チャネル攻撃対策)は、本章が示す Euler の定理による数学的正当性の証明とは異なるレイヤーの知識である**: [[公開鍵暗号方式]] の既存定義(Security Engineering 3e 第5章に基づく)は RSA を「暗号化 C ≡ M^e (mod N)、復号 M ≡ C^d (mod N) という単純な代数構造」として提示し、生の RSA が乗法準同型性ゆえに単体では安全でないためパディングが必須という運用上の注意に主眼を置く。一方、本章(MCS 第8章)は同じ代数構造がなぜ正しく機能するのか(Euler の定理 k^φ(n) ≡ 1 (mod n) と、公開鍵 e・秘密鍵 d が Z(p−1)(q−1) で互いに逆元であることから、復号が暗号化の逆演算になることの証明)を数論の基礎から積み上げて示す。両ソースを突き合わせることで、RSA という同一の暗号方式について「なぜ安全にしなければならないか(実装上の脆弱性)」と「そもそもなぜ正しく動くか(数学的正当性)」という相補的な2つの説明が揃う。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] ch.8 §8.10〜§8.11, [[公開鍵暗号方式]] が参照する Security Engineering 3e ch.5 §5.7) - 第8章はEulerのφ関数の明示公式 φ(n) = n・∏(1 − 1/pi)(nの素因数分解がp1^e1・…・pm^emのとき)を系8.10.11として**証明なしに**提示するが、第14章(Cardinality Rules)はまさにこの式を、[[包除原理]]という数論とは独立した数え上げの道具を使って証明する(§14.9.5: [0,n)のうちnと互いに素でない整数の集合を各素因数の倍数集合の和集合として捉え、その大きさを包除原理で計算する)。両章を突き合わせると、合同算術の枠組みの中で応用上必要な結果として天下り的に導入されたφ関数の明示公式が、数え上げの部(Part III)で初めて厳密な証明を与えられるという、第8章(数論)と第14章(数え上げ)という異なる部にまたがる依存関係が明確になる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] 系8.10.11, [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] §14.9.5) ## 未解決の問い - 本章は RSA の秘密鍵が n の素因数分解と同程度に困難であることを述べるが証明は演習(Problem 8.83)に委ねている。素因数分解と秘密鍵復元の計算量的な等価性(またはその限界)を厳密に扱う暗号理論のソースが ingest されたら、この主張を裏付けたい。 - Euler の定理は k^φ(n) − 1 の高速べき乗計算(fast exponentiation)を前提に RSA の暗号化・復号を効率化するが、本章は fast exponentiation のアルゴリズム自体の詳細(計算量・実装)には踏み込んでいない。アルゴリズム的な扱いをする他ソースとの突き合わせが未着手。 ## 関連 - [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] — 合同・環 Zn・乗法逆元・Euler の定理・Fermat の小定理 - [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] — 包除原理によるEulerのφ関数明示公式の証明 - [[最大公約数]] — gcd(k, n) = 1 と Zn での乗法逆元の存在が同値であることの土台 - [[公開鍵暗号方式]] — RSA の数学的正当性の証明に Euler の定理が使われる - [[素数]] — 素数 p では φ(p) = p − 1 となることが Euler の φ 関数の基礎になる - [[包除原理]] — Eulerのφ関数の明示公式の証明技法 ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 8, §8.6〜§8.10, Chapter 14 §14.9.5.