Chapter 15

数論の道具 — オイラー・中国剰余定理・離散対数

公開鍵暗号に必要な数学を、ここで一気に揃える. 16 章の RSA、17 章の楕円曲線暗号は、どれも「計算は簡単だが、逆算は絶望的に難しい」という一方向性に安全性を賭けている。
その一方向性を生み出すのが、この章で扱う数論の定理群である。 01・02・03 章で作った合同算術と群論の上に、公開鍵暗号の土台を組み上げる。

1. オイラーの φ 関数

定義

\(\varphi(n)\) = \(1\)から\(n\)までのうち、\(n\)と互いに素な数の個数。

例: \(\varphi(10)\) → \(\{1,3,7,9\}\) の 4 個 → \(\varphi(10)=4\)

計算公式

(a) \(p\)が素数: \(\varphi(p) = p-1\) （\(1,\dots,p-1\)すべてが\(p\)と互いに素）

(b) \(p\)が素数、\(k\geq1\): \(\varphi(p^k) = p^k - p^{k-1} = p^k\left(1-\frac1p\right)\)

導出: \(1\)から\(p^k\)のうち\(p^k\)と互いに素でないのは\(p\)の倍数だけ。 \(p\)の倍数は\(p, 2p, \dots, p^{k-1}\cdot p\)の\(p^{k-1}\)個。引けばよい ∎

(c) 乗法性: \(\gcd(m,n)=1\) なら \(\varphi(mn) = \varphi(m)\varphi(n)\) （導出は §3 の中国剰余定理から従う）

(d) 一般形: \(n = p_1^{e_1}\cdots p_r^{e_r}\) のとき

\[ \varphi(n) = n\prod_{i=1}^{r}\left(1 - \frac{1}{p_i}\right) \]

RSA で使う最重要ケース: \(n = pq\)（相異なる素数）のとき

\[ \boxed{\varphi(pq) = (p-1)(q-1)} \]

ここに RSA の安全性の急所がある. \(n = pq\)は公開される。しかし\(\varphi(n) = (p-1)(q-1)\)を計算するには\(p, q\)を知る必要がある。つまり \(\varphi(n)\)を求めること = \(n\)を素因数分解することとほぼ同等である。
鍵を作る人: \(p, q\)を自分で選んだので\(\varphi(n)\)を即座に計算できる
攻撃者: \(n\)しか知らないので、素因数分解しないと\(\varphi(n)\)が分からない
この非対称性が RSA そのものである（16 章）。

2. オイラーの定理

定理

\(\gcd(a,n)=1\) のとき:

\[ \boxed{a^{\varphi(n)} \equiv 1 \pmod n} \]

導出（群論から — 02 章の一般定理の適用）

\(n\)と互いに素な剰余類の集合\((\mathbb{Z}/n\mathbb{Z})^\ast\)は、掛け算について群をなす:

閉性: \(\gcd(a,n)=\gcd(b,n)=1\)なら\(\gcd(ab,n)=1\) ✓
逆元: 01 章の定理より存在 ✓

この群の位数はちょうど\(\varphi(n)\)（定義そのもの）。 02 章のラグランジュの定理より\(a^{|G|} = a^{\varphi(n)} = 1\) ∎

系（フェルマーの小定理）: \(n=p\)（素数）なら\(\varphi(p)=p-1\)なので\(a^{p-1}\equiv1 \pmod p\)

02 章で「ラグランジュの定理がフェルマーの小定理の正体」と述べた話が、ここでオイラーの定理という一般形に拡張された. 数論の定理に見えるが、本質は有限群では位数乗すると単位元に戻るという代数の事実である。

3. 中国剰余定理 (CRT)

定理

\(m_1,\dots,m_r\)が両々互いに素のとき、連立合同式

\[ x \equiv a_1 \pmod{m_1},\quad \dots,\quad x \equiv a_r \pmod{m_r} \]

は\(M = m_1\cdots m_r\)を法としてただ 1 つの解を持つ。

導出（構成的に解を作る）

\(M_i = M/m_i\)とおく。\(\gcd(M_i, m_i)=1\)（\(m_j\)たちが互いに素だから）なので、 01 章より逆元\(N_i = M_i^{-1} \bmod m_i\)が存在する。ここで

\[ \boxed{x = \sum_{i=1}^{r} a_i M_i N_i \bmod M} \]

とおく。これが解であることを確認する。法\(m_j\)で見ると:

\(i \neq j\)の項は\(M_i\)が\(m_j\)を因数に含むので\(\equiv 0\)
\(i = j\)の項は\(a_j M_j N_j \equiv a_j \cdot 1 = a_j\)（\(N_j\)の定義より）

よって\(x \equiv a_j \pmod{m_j}\)がすべての\(j\)で成立 ✓

一意性: 解が 2 つ\(x, x'\)あれば\(x - x'\)はすべての\(m_i\)で割り切れる。互いに素なので\(M\)で割り切れ、\(\bmod M\)では同じ ∎

実例

\[ x \equiv 2 \pmod 3, \quad x \equiv 3 \pmod 5, \quad x \equiv 2 \pmod 7 \]

\(M = 105\)、\(M_1=35, M_2=21, M_3=15\)。

\(N_1 = 35^{-1} \bmod 3\): \(35\equiv2\)、\(2\cdot2=4\equiv1\) → \(N_1=2\)
\(N_2 = 21^{-1}\bmod 5\): \(21\equiv1\) → \(N_2=1\)
\(N_3 = 15^{-1}\bmod 7\): \(15\equiv1\) → \(N_3=1\)

\[ x = 2\cdot35\cdot2 + 3\cdot21\cdot1 + 2\cdot15\cdot1 = 140+63+30 = 233 \equiv 23 \pmod{105} \]

検算: \(23 = 3\cdot7+2\) ✓、\(23=5\cdot4+3\) ✓、\(23=7\cdot3+2\) ✓

CRT の実用上の価値: RSA が 4 倍速くなる. RSA の復号\(m = c^d \bmod n\)（\(n=pq\)）は重い。そこで CRT を使う:
\(m_p = c^{d \bmod (p-1)} \bmod p\) を計算（法が半分の大きさ）
\(m_q = c^{d \bmod (q-1)} \bmod q\) を計算
CRT で\(m\)を復元
法のビット数が半分になると、乗算は約 1/4 のコストになる。 2 回やっても全体で約 4 倍高速。実際の RSA 実装（OpenSSL 等）はほぼ全部これを使っている。
ただし副作用がある: この最適化はフォールト攻撃の標的になる。 \(m_p\)の計算中に故意にエラーを起こさせると、出力から\(\gcd\)を使って\(q\)が求まってしまう（Bellcore 攻撃）。実装では計算結果の検証が必須である。

4. 位数と原始根

位数

\(\gcd(a,n)=1\)のとき、\(a^k \equiv 1 \pmod n\)となる最小の正整数\(k\)を\(a\)の位数という。

性質: 位数は\(\varphi(n)\)を割り切る（ラグランジュの定理）。

原始根

位数がちょうど\(\varphi(n)\)に等しい\(a\)を原始根という（03 章の原始元と同じ概念）。

存在定理: \(n\)が\(1, 2, 4, p^k, 2p^k\)（\(p\)は奇素数）の形のときのみ原始根が存在する。

個数: 存在するとき\(\varphi(\varphi(n))\)個。

5. 離散対数問題 (DLP)

定義

\(g\)を\(\mathbb{Z}_p^\ast\)の原始根とする。与えられた\(y\)に対し

\[ g^x \equiv y \pmod p \]

を満たす\(x\)を求める問題を離散対数問題という。

難しさの非対称性

方向	計算量	2048 ビットでの実時間
\(x \to y = g^x\)	\(O(\log x)\)（繰り返し二乗法、01 章）	ミリ秒
\(y \to x\)	最良でも準指数時間	現実的に不可能

既知のアルゴリズム:

手法	計算量	備考
総当たり	\(O(p)\)	論外
Baby-step Giant-step	\(O(\sqrt p)\)	メモリも\(O(\sqrt p)\)
Pollard の ρ	\(O(\sqrt p)\)	メモリ\(O(1)\)、実用的
Index Calculus	準指数\(L_p[1/3]\)	\(\mathbb{Z}_p^\ast\)では有効

ここが 17 章の楕円曲線暗号につながる決定的な点. \(\mathbb{Z}_p^\ast\)上の DLP には Index Calculus という準指数時間アルゴリズムが効く。だから安全性を保つには\(p\)を 2048 ビット以上にする必要がある。
ところが楕円曲線上の群には Index Calculus が適用できない（滑らかな数の概念が無いため）。使えるのは\(O(\sqrt n)\)の Pollard ρ だけ。したがって同じ安全性を、はるかに短い鍵で達成できる:
安全性レベル RSA/DH の鍵長楕円曲線の鍵長
112 ビット 2048 224
128 ビット 3072 256
256 ビット 15360 512
鍵が 1/10 以下。これが楕円曲線が主流になった理由である。

安全性レベル	RSA/DH の鍵長	楕円曲線の鍵長
112 ビット	2048	224
128 ビット	3072	256
256 ビット	15360	512

6. 素数判定 — 鍵生成に必須

RSA には 1024 ビット級の素数が 2 個必要。どうやって見つけるか。

素数定理

\(x\)以下の素数の個数\(\pi(x) \approx x/\ln x\)。

つまり\(n\)付近の数が素数である確率は約\(1/\ln n\)。 1024 ビットなら\(1/\ln(2^{1024}) \approx 1/710\)。偶数を除けば約 355 回に 1 回。ランダムに選んで判定を繰り返せば、すぐ見つかる。

フェルマー・テスト

\(a^{n-1} \equiv 1 \pmod n\) を満たさなければ\(n\)は合成数（フェルマーの小定理の対偶）。

弱点: カーマイケル数（561, 1105, 1729, …）はすべての\(a\)で通過してしまう。

ミラー・ラビン・テスト（実用の標準）

\(n-1 = 2^s d\)（\(d\)は奇数）と分解する。\(n\)が素数なら、任意の\(a\)について

\[ a^d \equiv 1 \pmod n \quad\text{または}\quad a^{2^rd}\equiv -1 \pmod n\ (\exists r < s) \]

なぜこれが強いのか: \(n\)が素数なら\(\mathbb{Z}_n\)は体（02 章）なので、 \(x^2 \equiv 1\)の解は\(x=\pm1\)の 2 つだけ。 \(a^{n-1}=1\)から平方根を順に取っていくと、必ず\(\pm1\)を経由するはずである。 それ以外の平方根（自明でない平方根）が見つかれば、体でない = 合成数と分かる。

誤り確率: 1 回のテストで合成数を素数と誤判定する確率は\(\leq 1/4\)。 \(k\)回繰り返せば\(\leq 4^{-k}\)。64 回で\(2^{-128}\) —— 宇宙が終わるまでに間違えない。

7. まとめ

道具	内容	使う場所
\(\varphi(n)\)	互いに素な数の個数。\(\varphi(pq)=(p-1)(q-1)\)	RSA の鍵生成
オイラーの定理	\(a^{\varphi(n)}\equiv1\)	RSA の正しさの証明
中国剰余定理	連立合同式を解く	RSA の高速化（4 倍）
原始根	位数が\(\varphi(n)\)の元	DH、ElGamal
離散対数問題	\(g^x=y\)から\(x\)を求める	DH・楕円曲線の安全性
ミラー・ラビン	確率的素数判定	鍵生成