数論中級

Intermediate Number Theory

中級（大学3-4年レベル）

この章について

数論中級は二部構成である。応用・実装編では、初級で学んだ定理を暗号や素数判定アルゴリズムに応用し、Python 実装とともに理解を深める。理論編では、2次剰余と平方剰余の相互法則、連分数、数論的関数、p進数体など、より深い理論を学ぶ。

前提知識

  • 初級レベルの内容（合同式、オイラーの定理、中国剰余定理、原始根）
  • 群論の基礎（位数、巡回群）があると望ましい

目次

応用・実装編

初級の定理を暗号・アルゴリズムに応用し、Python 実装とともに学ぶ。

A1. 合同式とモジュラ算術

合同式の応用と暗号理論への展開。

  • フェルマーの小定理の応用
  • RSA暗号・Diffie-Hellman
  • Python 実装例

A2. オイラー関数の応用

$\varphi$ 関数の計算とRSA鍵生成。

  • $\varphi$ 関数の計算公式
  • RSA鍵生成への応用
  • Python 実装例

A3. 中国剰余定理の応用

CRT-RSA高速化とセキュリティ。

  • 逐次的CRTアルゴリズム
  • CRT-RSAによる復号高速化
  • Python 実装例

A4. 離散対数問題

暗号の安全性を支える計算的困難性。

  • Baby-step Giant-step
  • Pollard's rho
  • Diffie-Hellman との関係

A5. Miller-Rabin 素数判定法

確率的素数判定アルゴリズム。

  • フェルマーテストの改良
  • 誤判定確率の解析
  • 実装上の注意

A6. バイナリ GCD

Stein のアルゴリズムによる高速GCD。

  • ビット演算による高速化
  • 正当性の証明と計算量
  • ユークリッド互除法との比較

A7. 楕円曲線

群構造と暗号への応用。

  • 楕円曲線の定義と群演算
  • Mordell-Weil の定理
  • 楕円曲線暗号（ECC）

理論編

2次剰余、連分数、p進数体など、より深い数論の理論を学ぶ。

T1. 2次剰余と相互法則

ルジャンドル記号、オイラーの規準、ガウスの「数学の宝石」。

T2. 素数の分布と素数定理

素数計数関数 $\pi(x)$、チェビシェフの評価、素数定理 $\pi(x) \sim x/\ln x$。

T3. 数論的関数

約数関数 $\sigma$、完全数、ディリクレ畳み込み。

T4. メビウス関数

メビウス関数 $\mu(n)$、反転公式、ディリクレ級数との関係。

T5. 連分数とペル方程式

有理近似、$x^2 - Dy^2 = 1$ の解法。

T6. 2次形式

$ax^2 + bxy + cy^2$ で表せる数。フェルマーの二平方定理。

T7. p進数体

p進絶対値、$\mathbb{Q}_p$ の構造、ヘンゼルの補題。

T8. 超越数と代数的無理数

数の分類理論、Liouville の定理、ディオファントス近似。

  • 代数的無理数と共役無理数
  • Liouville, Hermite-Lindemann, Gelfond-Schneider
  • Roth の定理と無理数測度

主要な定理

応用・実装編

RSA の正当性

$n = pq$（$p, q$ は素数）、$ed \equiv 1 \pmod{\varphi(n)}$ とすると、任意の $m \in \mathbb{Z}/n\mathbb{Z}$ に対して

$$m^{ed} \equiv m \pmod{n}$$

これはオイラーの定理 $m^{\varphi(n)} \equiv 1$ の直接的な応用である。

Miller-Rabin 判定法の誤判定確率

$n$ が合成数のとき、ランダムに選んだ基底 $a$ が「$n$ は素数」と誤判定する確率は高々 $1/4$ である。$k$ 回独立に試行すれば、誤判定確率は $(1/4)^k$ 以下となる。

Hasse の定理（楕円曲線）

有限体 $\mathbb{F}_p$ 上の楕円曲線 $E$ の有理点数 $\#E(\mathbb{F}_p)$ について、

$$|\#E(\mathbb{F}_p) - (p+1)| \le 2\sqrt{p}$$

理論編

素数定理

$\pi(x)$ を $x$ 以下の素数の個数とするとき、

$$\pi(x) \sim \frac{x}{\ln x} \quad (x \to \infty)$$

すなわち $\displaystyle\lim_{x \to \infty} \frac{\pi(x)}{x/\ln x} = 1$。より精密には $\pi(x) \sim \mathrm{Li}(x) = \int_2^x \frac{dt}{\ln t}$。

平方剰余の相互法則

$p, q$ を異なる奇素数とするとき、

$$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$$

メビウスの反転公式

$f(n) = \sum_{d \mid n} g(d)$ ならば $g(n) = \sum_{d \mid n} \mu(d) f(n/d)$

ここで $\mu$ はメビウス関数。

Liouville の定理

$\alpha$ が $n$ 次の代数的無理数ならば、ある定数 $c(\alpha) > 0$ が存在して、すべての有理数 $p/q$ に対し

$$\left|\alpha - \frac{p}{q}\right| > \frac{c(\alpha)}{q^n}$$

このレベルで理解できる応用

公開鍵暗号の実装

RSA 暗号では鍵生成にオイラー関数を、復号に中国剰余定理（CRT-RSA）を使う。Diffie-Hellman 鍵交換は離散対数問題の困難性に基づく。これらの暗号は、応用編 A1–A4 の内容で完全に理解できる。

素数判定と鍵生成

RSA 鍵の生成には大きな素数が必要。Miller-Rabin 判定法（A5）は実用上最も広く使われる確率的素数判定アルゴリズムで、OpenSSL や GnuPG の内部で動いている。

信号処理と数論的変換

数論変換（NTT）は、FFT を有限体上で行うもの。原始根を 1 の原始根の代わりに使う。浮動小数点誤差がなく、暗号計算や多倍長整数の乗算で使用される。

楕円曲線暗号（ECC）

楕円曲線（A7）上の離散対数問題は RSA より効率的な暗号を実現する。TLS 1.3 で標準となった ECDHE 鍵交換、Bitcoin の署名（ECDSA）など、現代のインターネットセキュリティの中核を担う。

学習のポイント

  • 理論から実装へ：オイラーの定理や CRT を暗号アルゴリズムに落とし込む力を養う
  • 計算量の意識：Baby-step Giant-step や バイナリ GCD など、アルゴリズムの効率性を比較・分析する
  • 確率的手法：Miller-Rabin のように「確率的に正しい」アルゴリズムの意義と限界を理解する
  • 代数と幾何の接点：楕円曲線を通じて、数論・代数・幾何の融合を体験する