数論中級ではどのようなことを学ぶか？

2次剰余・Legendre 記号・Quadratic Reciprocity（2次相互法則）・連分数と有理近似・p進数体・合同式の応用（RSA・Diffie-Hellman などの暗号アルゴリズム）・代数的整数の入門を扱う。

2次相互法則（Gauss の黄金定理）とは何か？

奇素数 $p, q$ に対して $\left(\rac{p}{q}\ ight)\left(\rac{q}{p}\ ight) = (-1)^{\rac{p-1}{2}\cdot\rac{q-1}{2}}$ が成立する。$p$ が $q$ の2次剰余かと $q$ が $p$ の2次剰余かが連動するという深い定理である。

p進数（$p$-adic numbers）とはどのような数体系か？

素数 $p$ に関してある意味で「完備」な数体系 $\mathbb{Q}_p$ である。$p$ の高冪が「小さい」という距離の下での $\mathbb{Q}$ の完備化で、$p$ 進 Hensel の補題・$p$ 進 L 関数などを扱うのに不可欠である。

数論中級

Intermediate Number Theory

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

この章について

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

前提知識

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

主要な定理

応用・実装編

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 \dfrac{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(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right) = (-1)^{\dfrac{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 - \dfrac{p}{q}\right| > \dfrac{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 のように「確率的に正しい」アルゴリズムの意義と限界を理解する
代数と幾何の接点：楕円曲線を通じて、数論・代数・幾何の融合を体験する

この章について

前提知識

目次

応用・実装編

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

A2. オイラー関数の応用

A3. 中国剰余定理の応用

A4. 離散対数問題

A5. Miller-Rabin 素数判定法

A6. バイナリ GCD

A7. 楕円曲線

理論編

T1. 2次剰余と相互法則

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

T3. 数論的関数

T4. メビウス関数

T5. 連分数とペル方程式

T6. 2次形式

T7. p進数体

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

T9. ピタゴラス数

アイゼンシュタイン整数（Eisenstein Integer）

カーマイケル関数（Carmichael Function）

クンマーの定理（Kummer's Theorem）

メルテンス関数

フォン・マンゴルト関数

ジョルダンのトーシェント関数

デデキントのプシー関数

ラマヌジャン和

ガウスの円問題

ディリクレの約数問題

過剰指数

アリコット数列

ウィーフェリッヒ素数

ウィルソン素数

フォーチュン数

完全トーシェント数

ユニタリ約数

プロス数

シェルピンスキー数

リーゼル数

カニンガム鎖

ラマヌジャン素数

均衡素数

スーパー素数

階乗素数

フィボナッチ素数

フェルマー擬素数

強擬素数

合同数

便利数（イドネアル数）

キネア数

テトラナッチ数

ペラン数列

ペル・リュカ数

シルベスター数列

カルキン・ウィルフ木

ゴロム数列

コラコフスキー数列

テュエ・モース数列

ルディン・シャピロ数列

ドゥッチ数列

三つ子素数

四つ子素数

陳素数

回文素数

循環素数

切り詰め可能素数

順列素数

安全素数

ピタゴラス素数

二重メルセンヌ数

素数階乗素数

NSW素数

二平方和の定理

ラグランジュの四平方定理

ウェアリングの問題

エルデシュ・シュトラウス予想

ズナームの問題

フェルマーの多角数定理