楕円曲線の有理点群の構造

$E (F_{q}) ≅ Z / n_{1} \times Z / n_{2}$ （ $n_{1} ∣ n_{2}$ , $n_{1} ∣ q - 1$ ）を使える。2 等分点の個数（ $x^{3} + a x + b$ の $F_{q}$ 内の根の数 $+ 1$ ）から $# E$ の偶奇や $E [2]$ の構造を判定できる。群の構造がわかっているとき、位数がちょうど $d$ の点の個数を求められる

前提

平方剰余による有理点の数え上げ（大学院数学代数幾何）
有限体上の楕円曲線の点の加算（大学数学暗号理論）

この技能までの道筋（62 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

約数の見つけ方（算数整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
群の位数と元の位数（大学数学代数学）
有限アーベル群の構造と部分群の個数（大学数学代数学）
剰余類環の単元群とオイラー関数（大学数学代数学）
3 次式までの展開と因数分解（数学I 数と式）
整式の除法（数学II 複素数と方程式）
剰余環のイデアルと単元の個数（大学数学代数学）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
平方根の意味と根号の簡単化（中学数学数と式）
根号の乗除と加減（中学数学数と式）
分母の有理化（中学数学数と式）
乗法公式・分配法則を使う根号の式の展開（中学数学数と式）
根号を含む式の計算と分母の有理化（数学I 数と式）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
1 次方程式の解き方（中学数学方程式）
比例・反比例の式とグラフ（中学数学関数）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
複素数と 2 次方程式の虚数解（数学II 複素数と方程式）
最小多項式と既約性の判定（大学数学代数学）
三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
三平方の定理（中学数学相似と三平方の定理）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
ベクトル空間・一次独立・基底・次元（大学数学線形代数）
拡大次数と次数の積の公式（大学数学代数学）
有限体の構造と部分体（大学数学代数学）
射影平面曲線と斉次化（大学院数学代数幾何）
平方剰余による有理点の数え上げ（大学院数学代数幾何）
ユークリッドの互除法（数学A 整数の性質）
1 次不定方程式の整数解（数学A 整数の性質）
法 $m$ での逆元（拡張ユークリッドの互除法）（大学数学暗号理論）
有限体上の楕円曲線の点の加算（大学数学暗号理論）

説明

有限体 $F_{q}$ （標数 $p \neq = 2, 3$ ）上の楕円曲線 $E : y^{2} = x^{3} + a x + b$ （ $4 a^{3} + 27 b^{2} \neq = 0$ ）の有理点全体 $E (F_{q})$ は、点の加算で有限アーベル群になります。この技能では、その群が必ず $Z / n_{1} \times Z / n_{2}$ （ $n_{1} ∣ n_{2}$ , $n_{1} ∣ q - 1$ ）の形になることを使って、点の個数 $# E (F_{q})$ と 2 等分点の情報から群の構造を決め、位数がちょうど $d$ の点の個数を求めます。暗号で使う曲線の点の位数を調べるときや、大学院入試で「位数 $d$ の点はいくつあるか」を問われたときに使います。

なぜそうしてよいのか

まず、構造定理 $E (F_{q}) ≅ Z / n_{1} \times Z / n_{2}$ （ $n_{1} ∣ n_{2}$ ）の背景を述べます。 $p$ で割り切れない $m$ に対して、代数閉包 $F_{q}$ 上で $m P = O$ をみたす点 $P$ 全体（ $m$ 等分点群 $E [m]$ ）は $Z / m \times Z / m$ と同型で、ちょうど $m^{2}$ 個です（ $E [p]$ は $O$ だけか $Z / p$ です）。これは楕円曲線の基本事実として認めます。すると有限アーベル群 $E (F_{q})$ を巡回群の積 $Z / n_{1} \times \dots \times Z / n_{k}$ （ $n_{1} ∣ n_{2} ∣ \dots ∣ n_{k}$ , $n_{1} > 1$ ）に分解したとき、 $k \geq 3$ なら $n_{1}$ の素因数 $ℓ$ について位数 $ℓ$ 以下の元（ $ℓ P = O$ の元）が $ℓ^{3}$ 個以上あることになり、 $E [ℓ]$ が高々 $ℓ^{2}$ 個しかないことに反します。よって巡回因子は高々 2 個です。さらに $n_{1} ∣ q - 1$ という制約があり（ $E [n_{1}]$ 全体が $F_{q}$ 上にあると、ヴェイユ対と呼ばれる対応から 1 の原始 $n_{1}$ 乗根が $F_{q}$ に入ることが従う、という事実です）、これも認めて使います。

次に 2 等分点です。 $P = (x, y)$ の逆元は $- P = (x, - y)$ なので、 $2 P = O$ すなわち $P = - P$ となるのは $y = - y$ 、つまり（ $p \neq = 2$ より） $y = 0$ のときです。したがって $F_{q}$ 上の 2 等分点は、 $O$ と、 $x^{3} + a x + b = 0$ の $F_{q}$ 内の根 $x_{0}$ に対する点 $(x_{0}, 0)$ です。根の個数を $r$ とすると $# E (F_{q}) [2] = r + 1$ です。3 次式は 2 つの根が $F_{q}$ にあれば、残りの根も（根と係数の関係から） $F_{q}$ に入るので、 $r \in {0, 1, 3}$ です。 $r = 0$ なら位数 2 の元がなく $# E$ は奇数、 $r = 1$ なら $E (F_{q}) [2] ≅ Z /2$ で 2 部分は巡回（ $n_{1}$ は奇数で $n_{2}$ は偶数）、 $r = 3$ なら $E (F_{q}) [2] ≅ Z /2 \times Z /2$ で $n_{1}$ が偶数、特に $4 ∣ # E$ です。

最後に位数の数え上げです。 $G = Z / n_{1} \times Z / n_{2}$ で $d P = O$ をみたす元の個数は、各成分で $d x \equiv 0 (mod n_{i})$ の解が $g cd (d, n_{i})$ 個あることから $f (d) = g cd (d, n_{1}) g cd (d, n_{2})$ 個です。位数が $d$ を割り切る元の個数が $f (d)$ なので、そこから位数が $d$ の真の約数である元を除けば、位数がちょうど $d$ の元の個数が得られます。 $d = ℓ^{k}$ （ $ℓ$ は素数）なら、真の約数はすべて $ℓ^{k - 1}$ を割るので、答えは $f (ℓ^{k}) - f (ℓ^{k - 1})$ です。

手順

曲線 $y^{2} = x^{3} + a x + b$ と $F_{q}$ （ $p \neq = 2, 3$ , $4 a^{3} + 27 b^{2} \neq = 0$ ）を確認し、平方剰余による数え上げ $# E (F_{q}) = q + 1 + \sum_{x} χ (x^{3} + a x + b)$ で点の個数 $N$ を求める（与えられていればそれを使う）。
$x^{3} + a x + b$ の $F_{q}$ 内の根の個数 $r \in {0, 1, 3}$ を調べ、 $E (F_{q}) [2]$ が自明・ $Z /2$ ・ $Z /2 \times Z /2$ のどれかを決める（2 等分点は $O$ を含めて $r + 1$ 個）。
$n_{1} n_{2} = N$ , $n_{1} ∣ n_{2}$ , $n_{1} ∣ q - 1$ をみたす候補 $(n_{1}, n_{2})$ を書き出し、手順 2 の 2 部分の情報（ $r = 3$ なら $n_{1}$ は偶数、 $r \leq 1$ なら $n_{1}$ は奇数）などで 1 つに絞る。絞れなければ点の加算で特定の点の位数を調べる。
$d P = O$ をみたす点の個数 $f (d) = g cd (d, n_{1}) g cd (d, n_{2})$ を計算する。
位数がちょうど $d$ の点の個数を、 $f (d)$ から位数が $d$ の真の約数である点を引いて求める。 $d = ℓ^{k}$ なら $f (ℓ^{k}) - f (ℓ^{k - 1})$ 。

例題

$F_{7}$ 上の楕円曲線 $E : y^{2} = x^{3} - x$ を考える。 $E (F_{7})$ （無限遠点 $O$ を含む）の中で、位数がちょうど $4$ の点の個数を求めよ。

例題の解答

（手順 1） $4 a^{3} + 27 b^{2} = 4 \cdot (- 1)^{3} = - 4 \neq \equiv 0 (mod 7)$ なので楕円曲線である。 $mod 7$ の平方剰余は $1, 2, 4$ 。 $x = 0, \dots, 6$ について $x^{3} - x$ は順に $0, 0, 6, 3, 4, 1, 0$ なので、 $χ$ の値は $0, 0, - 1, - 1, 1, 1, 0$ 、和は $0$ 。よって $N = # E (F_{7}) = 7 + 1 + 0 = 8$ 。

（手順 2） $x^{3} - x = x (x - 1) (x + 1)$ は $F_{7}$ に根 $0, 1, 6$ をもつので $r = 3$ 。2 等分点は $O, (0, 0), (1, 0), (6, 0)$ の 4 個で、 $E (F_{7}) [2] ≅ Z /2 \times Z /2$ 。

（手順 3） $n_{1} n_{2} = 8$ , $n_{1} ∣ n_{2}$ の候補は $(1, 8)$ と $(2, 4)$ 。 $r = 3$ より $n_{1}$ は偶数なので $(n_{1}, n_{2}) = (2, 4)$ （ $n_{1} = 2 ∣ 7 - 1$ も満たす）。よって $E (F_{7}) ≅ Z /2 \times Z /4$ 。

（手順 4） $f (4) = g cd (4, 2) g cd (4, 4) = 2 \cdot 4 = 8$ , $f (2) = g cd (2, 2) g cd (2, 4) = 2 \cdot 2 = 4$ 。

（手順 5） $d = 4 = 2^{2}$ なので、位数がちょうど 4 の点は $f (4) - f (2) = 8 - 4 = 4$ 個。

（確かめ）残りの点は $x = 4$ の $(4, 2), (4, 5)$ と $x = 5$ の $(5, 1), (5, 6)$ の 4 個。たとえば $P = (4, 2)$ では $λ = \frac{3 \cdot 16 - 1}{2 \cdot 2} \equiv 5 \cdot 4^{- 1} \equiv 5 \cdot 2 \equiv 3$ , $x_{3} = 9 - 8 = 1$ , $y_{3} = 3 (4 - 1) - 2 \equiv 0$ で $2 P = (1, 0) \neq = O$ , したがって $P$ の位数は 4 であり、結果と合う。

答え: $4$

よくある誤り

$x^{3} + a x + b$ の $F_{q}$ 内の根が 2 個の場合を考えてしまう誤り。正しくは、2 根が $F_{q}$ にあれば 3 根目 $= - (x_{1} + x_{2})$ （ $x^{2}$ の係数が 0 だから）も $F_{q}$ にあるので、根の個数は $0, 1, 3$ のどれかである。
2 等分点の個数を根の個数 $r$ そのものとしてしまう誤り。正しくは $O$ も $2 O = O$ をみたすので $# E (F_{q}) [2] = r + 1$ であり、位数がちょうど 2 の点が $r$ 個である（例: $r = 3$ なら $E [2]$ は 4 点）。
点の個数だけで群の構造を決めてしまう誤り。たとえば $N = 8$ でも $Z /8$ と $Z /2 \times Z /4$ の 2 通りがありうる。正しくは 2 等分点の個数（ $r = 1$ なら $Z /8$ , $r = 3$ なら $Z /2 \times Z /4$ ）や $n_{1} ∣ q - 1$ で絞る。たとえば $F_{5}$ 上で $N = 9$ なら $3 ∤ 5 - 1$ より $Z /3 \times Z /3$ はありえず $Z /9$ に決まる。
位数がちょうど $d$ の点の個数を $f (d) = g cd (d, n_{1}) g cd (d, n_{2})$ のままにしてしまう誤り。 $f (d)$ は位数が $d$ を割り切る点（ $O$ を含む）の個数である。正しくは真の約数の分を引き、 $Z /2 \times Z /4$ の位数 4 の点は $8 - 4 = 4$ 個。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
有限体 $F_{11}$ 上の楕円曲線 $E : y^{2} = x^{3} - 4 x$ を考える。 $E$ の $F_{11}$ 有理点全体 $E (F_{11})$ （無限遠点 $O$ を含む）は、点の加法によりアーベル群をなし、その位数は $# E (F_{11}) = 12$ であることが知られている。 $E (F_{11})$ の元のうち、位数がちょうど $6$ であるものの個数を求めよ。

この技能を使う問題

この技能の次に学べること

フロベニウスが整数になる場合の有理点群（大学院数学代数幾何）
超特異曲線と CM をもつ楕円曲線の点の数（大学院数学代数幾何）