有限体と楕円曲線

10 時の 5 時間後は 15 時ですが、時計の文字盤では 3 時です。 12 を超えたら 12 を引く——これが mod 12 の世界です。 数直線ではなく円周の上で計算していることになります。

なぜこれが暗号に効くのか: 何回足しても何回掛けても、 結果は必ず 0..11 の 12 個のどれかです。値が絶対に外へ出ない。 これが「固定長で扱える」の正体です。

a ≡ b (mod p) は「a − b が p の倍数」という意味です。 15 ≡ 3 (mod 12) は、15 と 3 が等しいのではなく、 12 で巻いた世界では同じ場所に来るということ。

15 ≡ 3 ≡ −9 ≡ 27　(mod 12)

ここが分岐点です。 ≡ で結ばれた数は無限にあります。 その無限の仲間から代表を 1 つ選ぶのが次のステップで、 プログラムが落ちるのはたいていそこです。

15, 3, −9, 27 はどれも mod 12 では同じものですが、 体の元として書くときは 0..11 の代表 3 に統一します。 この統一を正規化と呼びます。

−3 mod 7 = 4　　（−3 + 7 = 4。「余り」ではなく「巻いた先」で考える）
30 mod 7 = 2　　17 mod 7 = 3　　0 mod 7 = 0

なぜ 0..p−1 なのか: どれを選んでも数学的には同じですが、 比較・保存・テストのためには表現が 1 つに決まっていなければ困るから。 数学の都合ではなく、実装の都合で決めた約束です。

多くの言語の % は符号を引きずります。 Python の -3 % 7 は 4 になりますが、 C / Java / JavaScript / Rust の -3 % 7 は -3 です。

正しい正規化: ((n % p) + p) % p

このノートの JS もこの 1 行で書いています。 「mod を取ったつもり」で負の値が残ると、値としては正しいのに 他の関数と噛み合わなくなります。次の実測がまさにそれです。

集合 G と演算 ∗ が群であるとは、次の 4 つが成り立つことです。

① 閉じている: a ∗ b は必ず G の中
② 結合則: (a ∗ b) ∗ c = a ∗ (b ∗ c)
③ 単位元 e がある: a ∗ e = e ∗ a = a
④ 逆元がある: 各 a に a ∗ a⁻¹ = e となる a⁻¹ が存在

a ∗ b = b ∗ a（可換）は別条件で、 満たすものをアーベル群と呼びます。暗号で使う群はたいてい可換です。

群の正体は「行って、戻れる」です。 単位元があるから「何もしない」が書けて、逆元があるから「元に戻す」が書ける。 暗号は「戻せない」を作りたいのに、道具の側は戻せる必要がある—— この緊張が離散対数（⑧）で効いてきます。

下の 2 行が今週の主役です。 F_p* の乗法群と、楕円曲線の点の群。 この 2 つはまったく違う見た目をしていて、群としては同じ形をしています。 だから ⑧ で見るように、離散対数問題も同じ言葉で書けます。

環は + と × の両方があり、分配則 a(b+c) = ab + ac が成り立つ世界です。 加法については群（0 があり、−a がある）ですが、 乗法の逆元は要求されません。

例: 整数 Z。2 × ? = 1 を満たす整数はありません。 例: Z/nZ（n で割った余り、n は素数でなくてよい）。

環でできることは「+ と × と、その組み合わせ」だけです。 Week 1 の回路が「加算ゲートと乗算ゲートしかない」のは、 この定義に演算が 2 つしか無いことの直接の帰結です。 比較も分岐も、環の定義のどこにも書いてありません。

体は環であって、さらに 0 以外のすべての元に乗法逆元があるもの。 これでようやく四則が揃います。

群 ⊂ 環 ⊂ 体　　（できることが増えるほど、条件は厳しくなる）

有理数・実数は無限個の元を持つ体。有限体は元の個数が有限な体で、 要素数を位数と呼びます。

位数は必ず素数のべき pⁿ です。 n = 1 なら F_p（このノートの主役）、 n ≥ 2 なら拡大体 F_{p^n}—— 既約多項式の根を追加して作る世界で、Week 0 のスライドの後半に出てきます。 この講座の課題で使うのはほぼ F_p の方なので、ここでは名前だけ置いておきます。

同じ言葉で 2 つのものを指すので、最初に分けておきます。

群の位数: 群に含まれる元の個数
元の位数: gⁿ = 1 となる最小の正整数 n

混同しやすいのは、しばしば一致するからです。 F_7* の群の位数は 6、そして元 3 の位数も 6。 一致する元のことを生成元と呼びます。

F_7* = {1, 2, 3, 4, 5, 6}（0 を除いた 6 個）で、3 のべきを並べます。

3¹ = 3　3² = 9 ≡ 2　3³ = 6 ≡ 6
3⁴ = 18 ≡ 4　3⁵ = 12 ≡ 5　3⁶ = 15 ≡ 1

出てきたのは 3, 2, 6, 4, 5, 1——6 個すべてが 1 回ずつ。 そして 6 乗で 1 に戻り、そこから同じ列を繰り返します。 3 は F₇^* の生成元であり、この群は巡回群です。

順番に注目してください。 3, 2, 6, 4, 5, 1 は 大小の順ではありません。⑤ で見たとおり、掛け算は順序を壊します。 この「バラバラさ」が、⑧ の一方向性の材料になります。

同じ F_7* で、今度は 2 のべきを並べます。

2¹ = 2　2² = 4　2³ = 8 ≡ 1　→ 以降 2, 4, 1 の繰り返し

2 の位数は 3。到達できるのは {1, 2, 4} の 3 個だけで、 これは F₇^* の部分群です。

ラグランジュの定理: 元の位数は必ず群の位数を割り切ります。 6 の約数は 1, 2, 3, 6 なので、F_7* の元の位数は この 4 通りしかありえません（実際: 1 → 1、6 → 2、2 と 4 → 3、3 と 5 → 6）。 群の位数が素数なら、単位元以外は全部生成元になります—— ⑦ の楕円曲線で、この事実がそのまま出てきます。

Week 3 の講義スライドは、フーリエ変換の評価点として 位数 n の 1 の根 ω を使います。定義はこうです。

ωⁿ = 1 かつ ω⁰, ω¹, …, ωⁿ⁻¹ がすべて異なる

これは「ω の位数がちょうど n」と言っているだけです。 スライドの例は F₇ で ω = 2—— 上で見た「2 の位数は 3」がそのまま 「2 は位数 3 の 1 の根」になります。

H = {1, ω, ω²} = {1, 2, 4} ⊂ F₇^*

同じものに 2 つの名前が付いているだけです。 群の言葉では「位数 3 の元が生成する部分群」、 多項式の言葉では「フーリエ変換の評価点の集合」。 Week 3 以降で多項式を扱うとき、この節に戻れば下地は済んでいます。

体 F_p（p > 3）上の楕円曲線は、次の式を満たす点の集合です。

y² = x³ + a·x + b　　(a, b ∈ F_p)

ただし、次の条件を満たすものだけを楕円曲線と呼びます。

4a³ + 27b² ≠ 0　(mod p)

これは何の条件か: 右辺 x³ + ax + b が重根を持たない、という条件です。 重根があると曲線に尖った点や自分自身と交わる点ができ、 そこでは接線が 1 本に決まりません。 接線が決まらないと 2 倍算が定義できないので、群になりません。 ラボ B で a = 0, b = 0 を選ぶと、この条件で弾かれる様子が見られます。

方程式を満たす点だけでは群になりません。単位元がないからです。 そこで仮想的な点 O（無限遠点）を 1 つ追加します。

E = {O} ∪ { (x, y) ∈ F_p × F_p ｜ y² = x³ + ax + b }

O は「y 軸方向の無限の彼方」だと思ってください。 すべての垂直線が O を通る、と約束します。 そう約束すると「垂直線も 3 点で交わる」ことになり、 次の加法の定義に例外が要らなくなります。 数学が先で記号が後ではなく、都合のいい点を足して形を整えているのが実際です。

出発点は 1 つの事実です。3 次曲線と直線は、ちょうど 3 点で交わる （接する場合は 2 重に数え、垂直線は O を 3 点目に数える）。

2 点 P, Q を決める → 直線が決まる → 3 点目 R が自動的に決まる

そこで P + Q := −R（R を x 軸に関して反転した点）と定めます。

なぜわざわざ反転するのか: 反転せずに P + Q := R と決めると、 単位元が作れません。 「一直線上の 3 点の和は O」と約束すると、 P + Q + R = O つまり P + Q = −R となり、 O が単位元、x 軸反転が逆元、という群の形にぴたりと収まります。 結合則が成り立つことの証明だけは重く（射影幾何やベズーの定理を使う）、 ここでは事実として使います。

「y を反転しても曲線上にある」のは、方程式の左辺が y² だからです。 だから点は必ず上下 2 個ずつペアで現れます—— ラボ B の散布図で、点が中央の線に関して対称に並ぶのはこれが理由です。 例外は y = 0 の点だけで、そこは自分自身が自分の逆元になります。

直線の傾き λ を求めて、3 点目を計算します。場合分けは 2 つだけです。

弦（P ≠ Q）:　λ = (y₂ − y₁) / (x₂ − x₁)
接線（P = Q）:　λ = (3x₁² + a) / (2y₁)

x₃ = λ² − x₁ − x₂
y₃ = λ(x₁ − x₃) − y₁

この「/」は有限体の割り算——つまり (x₂ − x₁)⁻¹ や (2y₁)⁻¹ を掛けることです。 ④ で作った逆元が、ここで初めて実戦投入されます。

y₃ の式に注意: λ(x₁ − x₃) − y₁ であって λ(x₃ − x₁) + y₁ ではありません。 符号の中に「x 軸反転」が畳み込まれています。 Week 3 の課題 README も 「乗らないときは公式のどこか（特に y_R の符号）が間違っています」と警告しています。

① x₁ = x₂ かつ y₁ = −y₂ の場合: 分母 x₂ − x₁ = 0 → P + (−P) = O
② P = Q かつ y₁ = 0 の場合: 分母 2y₁ = 0 → 2P = O

④ の伏線を回収します。 0 に逆元が無いので、この 2 つは「計算できない」のではなく 「結果が O である」と定義するしかありません。 幾何で言えばどちらも垂直線—— ② は y = 0 の点での接線が垂直になる場合です。 「0 で割れない」という体の性質が、そのまま群の例外処理になっている。

ラボ B で y² = x³ + x over F₁₁ を選ぶと、 (0, 0) という y = 0 の点が現れます。 これを生成点にすると 2P = O、位数はちょうど 2 です。