楕円曲線暗号の深い話：リーマン・ロッホの定理から加法則を導く

楕円曲線の定義

標数が2, 3でない体K上の楕円曲線とは、ワイエルシュトラス標準形

E : y² = x³ + ax + b   (a, b ∈ K, 判別式 Δ = -16(4a³ + 27b²) ≠ 0)

で定義される非特異な平面3次曲線に、無限遠点Oを1点加えたものです。判別式が0でない という条件は、曲線が特異点(尖点や自己交差点)を持たないことを保証しています。 E(K)で、Kに座標を持つE上の点(Oを含む)全体の 集合を表します。

因子(divisor)とは何か

曲線E上の因子とは、E上の点(代数的閉包上で定義される点、 いわゆるWeil点)を有限個選び、それぞれに整数の係数を付けた形式和のことです。

D = Σ n_P [P]   (P は E 上の点、n_P ∈ ℤ、有限個を除き n_P = 0)

因子全体は自由アーベル群Div(E)をなし、deg(D) = Σ n_Pを次数と 呼びます。次数0の因子全体は部分群Div⁰(E)を成します。

E上の有理関数f(ゼロ写像でないもの)に対しては、主因子

div(f) = Σ_P ord_P(f) · [P]

が定まります。ここでord_P(f)は、点Pにおけるfの零点の位数 (負なら極の位数)です。有理関数の零点の個数と極の個数は(重複度込みで)常に一致するため、 主因子の次数は必ず0になります。

2つの因子D₁, D₂が、ある有理関数fによってD₁ - D₂ = div(f)と 書けるとき、D₁とD₂は線形同値(D₁ ∼ D₂)である といいます。次数0の因子を線形同値で割った商群をPic⁰(E)(またはCl⁰(E))と 書き、因子類群と呼びます。

リーマン・ロッホの定理

種数gの非特異射影代数曲線C上の因子Dに対して、

L(D) = { f : 有理関数 | div(f) + D ≥ 0 } ∪ {0}

というK-ベクトル空間を考え、l(D) = dim L(D)とします。直感的には、 l(D)は「因子Dで許される極の位数に収まる有理関数がどれだけあるか」を 数えたものです。リーマン・ロッホの定理は、標準因子(標準微分の因子)K_C を用いて、次の等式を主張します。

l(D) - l(K_C - D) = deg(D) - g + 1

楕円曲線は種数g = 1であり、さらに楕円曲線の標準因子K_Cは0と線形同値 (K_C ∼ 0、楕円曲線が至る所消えない正則な微分形式を持つことに対応)という特別な性質を 持ちます。これを代入すると、

l(D) - l(-D) = deg(D)

まで簡単になります。deg(D) > 0のとき、次数が負の因子に対応する空間はl(-D) = 0 となる(次数が負の因子を持つ有理関数は存在しない)ため、次の重要な系が得られます。

E(K) と Pic⁰(E) の同型：加法則の正体

ここからが本題です。無限遠点Oを固定し、写像

φ : E(K) → Pic⁰(E),   P ↦ [P] - [O]

を考えます。これが全単射であることを、上のリーマン・ロッホの系から示せます。

任意の次数0の因子D ∈ Div⁰(E)を取り、D' = D + [O]とするとdeg(D') = 1。 上の系よりl(D') = 1なので、D'に線形同値な有効因子(係数がすべて0以上の因子)は、 次数1すなわち「点1個」の形[P]にちょうど1つだけ定まります。よって

D + [O] ∼ [P]  ⟺  D ∼ [P] - [O]

となり、Dの線形同値類はただ1つの点Pによって一意に表されます。これはまさに φが全単射であることを意味しています。

Pic⁰(E)は因子の形式和という自然な群構造(単位元は0という因子類、 すなわち主因子のクラス)を持つアーベル群です。φが全単射である以上、この群構造を φでE(K)に「移植」することができます。つまり

P ⊕ Q := φ⁻¹( φ(P) + φ(Q) )

と定義すれば、E(K)はアーベル群になります。これが楕円曲線の加法群構造の、 代数幾何的な定義そのものです。

なぜ「同一直線上の3点の和はゼロ」になるのか

最後に、教科書でおなじみの幾何学的な加法則(直線とレレレの3交点)が、上の抽象的な定義と 一致することを見ておきます。E上の3点P, Q, Rが同一直線L上に あるとします。3次曲線と直線は(重複度込みで)ちょうど3点で交わるので、Lを定義する 1次式l(x, y)に対して、有理関数f = l / z(斉次座標での適切な正規化)を 考えると、

div(f) = [P] + [Q] + [R] - 3[O]

が成り立ちます(直線Lによる3つの零点P, Q, Rと、無限遠点Oにおける 3位の極が対応)。div(f)は主因子なので、これは0と線形同値、すなわち

[P] + [Q] + [R] - 3[O] ∼ 0
⟺ ([P] - [O]) + ([Q] - [O]) + ([R] - [O]) ∼ 0
⟺ φ(P) + φ(Q) + φ(R) = 0 (Pic⁰(E) の中で)
⟺ P ⊕ Q ⊕ R = O (E(K) の中で)

となります。これが「同一直線上の3点の和はO(単位元)」という、あの幾何学的な 加法則の正体です。実際にECCの実装で使われる加法公式(2点を通る直線を引き、3つ目の交点を x軸(標数によっては別の対称性)で折り返す、という手順)は、このdiv(f) ∼ 0という 関係を具体的な多項式演算に落とし込んだものに他なりません。

まとめ

• 楕円曲線上の点全体は、因子類群Pic⁰(E)との全単射φ: P ↦ [P]-[O]を持つ
• この全単射は、種数1・標準因子が0に同値という楕円曲線特有の性質を使ったリーマン・ロッホの定理から従う
• 群構造はPic⁰(E)からφを通じてE(K)に移植されたものである
• 「同一直線上の3点の和がゼロ」という幾何学的加法則は、直線の方程式が定める主因子が0に同値であることの言い換えにすぎない