暗号理論の問題

難易度 4大学院入試の標準レベル証明問題大学数学暗号理論

$K$ を標数が $2$ でも $3$ でもない体とし、 $a, b \in K$ は $4 a^{3} + 27 b^{2} \neq = 0$ をみたすとする。 $f (x) = x^{3} + a x + b$ とおき、楕円曲線
$E : y^{2} = f (x)$
の $K$ 有理点全体に無限遠点 $O$ を加えた集合 $E (K)$ を、通常の加法（ $O$ が単位元）で群と考える。 $4 a^{3} + 27 b^{2} \neq = 0$ のとき $f (x)$ は重根をもたないこと、および次の事実は用いてよい。
- 点 $P = (x_{0}, y_{0})$ に対し $- P = (x_{0}, - y_{0})$ である。 $x$ 座標が等しい 2 つのアフィン点 $Q, R$ は $R = Q$ または $R = - Q$ をみたす。
- $y_{0} \neq = 0$ のとき、 $2 P$ はアフィン点であり、 $λ = \frac{3 x _{0}^{2} + a}{2 y _{0}}$ とおくと、 $2 P$ の $x$ 座標は $λ^{2} - 2 x_{0}$ である。 $y_{0} = 0$ のときは $2 P = O$ である。

さらに
$ψ_{3} (x) = 3 x^{4} + 6 a x^{2} + 12 b x - a^{2}$
とおく。 $E (K)$ のアフィン点 $P = (x_{0}, y_{0})$ について、「 $P$ の位数が $3$ であるための必要十分条件は $ψ_{3} (x_{0}) = 0$ である」ことを証明せよ。

この問題で使うもの

有限体上の楕円曲線の点の加算（説明と入口の問題）
楕円曲線のスカラー倍と点の位数（説明と入口の問題）
多項式の微分（説明と入口の問題）

この問題を解けるようになるまで（29 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

位数が $3$ であることを $2 P = - P$ と言い換え、それを座標の条件に直そう。 $y_{0} = 0$ かどうかで場合分けが必要になる。

ヒント 2

$ψ_{3} (x) = 2 f (x) f^{''} (x) - f^{'} (x)^{2}$ と書けることを確かめておくと、 $y_{0} = 0$ の場合と $y_{0} \neq = 0$ の場合の両方で役に立つ。

ヒント 3

$y_{0} \neq = 0$ のとき、 $2 P = - P$ は「 $2 P$ の $x$ 座標が $x_{0}$ 」と同値（ $2 P = P$ は起こらない）。 $λ^{2} - 2 x_{0} = x_{0}$ を分母を払って整理し、 $y_{0}^{2} = f (x_{0})$ を代入する。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$P \neq = O$ から、位数が $3$ であることを $3 P = O$ 、さらに $2 P = - P$ と同値に言い換えている（2 点）
$y_{0} = 0$ の場合、 $3 P = P \neq = O$ を示し、かつ $f$ が重根をもたないことから $ψ_{3} (x_{0}) = - f^{'} (x_{0})^{2} \neq = 0$ を示している（3 点）
$y_{0} \neq = 0$ の場合、 $2 P = - P$ と「 $2 P$ の $x$ 座標が $x_{0}$ 」が同値であることを、 $2 P = P$ が起こらない理由を添えて示している（2 点）
$λ^{2} = 3 x_{0}$ を $4 y_{0}^{2} \neq = 0$ を掛けて整理し、 $y_{0}^{2} = f (x_{0})$ を代入して $ψ_{3} (x_{0}) = 0$ と同値であることを計算で示している（3 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

方針. $P \neq = O$ なので、 $P$ の位数が $3$ であることは $3 P = O$ 、すなわち $2 P = - P$ と同値である。 $y_{0} = 0$ の場合と $y_{0} \neq = 0$ の場合に分け、後者では $2 P = - P$ を $x$ 座標の等式に言い換えて $ψ_{3} (x_{0}) = 0$ を導く。

準備 1（位数 3 の言い換え）. $P$ はアフィン点なので $P \neq = O$ であり、位数は $1$ ではない。よって「 $P$ の位数が $3$ 」 $⟺$ 「 $3 P = O$ 」である（ $3 P = O$ なら位数は $3$ の約数で $1$ でないから $3$ 。逆は位数の定義から）。群の演算で $3 P = 2 P + P$ だから、両辺に $- P$ を加えて
$3 P = O ⟺ 2 P = - P . (1)$

準備 2（ $ψ_{3}$ の書き換え）. $f^{'} (x) = 3 x^{2} + a$ 、 $f^{''} (x) = 6 x$ であり、
$2 f (x) f^{''} (x) - f^{'} (x)^{2} = 12 x (x^{3} + a x + b) - (3 x^{2} + a)^{2} = 12 x^{4} + 12 a x^{2} + 12 b x - 9 x^{4} - 6 a x^{2} - a^{2} = ψ_{3} (x) .$
よって
$ψ_{3} (x) = 2 f (x) f^{''} (x) - f^{'} (x)^{2} . (2)$

場合 1: $y_{0} = 0$ のとき. このとき $f (x_{0}) = y_{0}^{2} = 0$ である。
- 与えられた事実より $2 P = O$ なので、 $3 P = 2 P + P = P \neq = O$ 。よって $P$ の位数は $3$ ではない。
- 一方、 $(2)$ より $ψ_{3} (x_{0}) = 2 \cdot 0 \cdot f^{''} (x_{0}) - f^{'} (x_{0})^{2} = - f^{'} (x_{0})^{2}$ 。もし $f^{'} (x_{0}) = 0$ なら、 $f (x_{0}) = f^{'} (x_{0}) = 0$ より $x_{0}$ は $f$ の重根となり、 $f$ が重根をもたないことに反する。よって $f^{'} (x_{0}) \neq = 0$ で、 $ψ_{3} (x_{0}) \neq = 0$ 。

したがってこの場合、「位数が $3$ 」と「 $ψ_{3} (x_{0}) = 0$ 」はともに偽であり、同値が成り立つ。

場合 2: $y_{0} \neq = 0$ のとき. 与えられた事実より $2 P$ はアフィン点で、その $x$ 座標は $x_{2} = λ^{2} - 2 x_{0}$ 、 $λ = \frac{3 x _{0}^{2} + a}{2 y _{0}}$ である（標数が $2$ でないので $2 y_{0} \neq = 0$ ）。

(i) $2 P = - P ⟺ x_{2} = x_{0}$ を示す。 $2 P = - P$ なら、 $- P = (x_{0}, - y_{0})$ より $x_{2} = x_{0}$ 。逆に $x_{2} = x_{0}$ なら、 $2 P$ と $P$ は $x$ 座標が等しいアフィン点なので $2 P = P$ または $2 P = - P$ 。 $2 P = P$ とすると両辺に $- P$ を加えて $P = O$ となり、 $P$ がアフィン点であることに反する。よって $2 P = - P$ 。

(ii) $x_{2} = x_{0} ⟺ ψ_{3} (x_{0}) = 0$ を示す。
$x_{2} = x_{0} ⟺ λ^{2} = 3 x_{0} ⟺ \frac{( 3 x _{0}^{2} + a ) ^{2}}{4 y _{0}^{2}} = 3 x_{0} ⟺ (3 x_{0}^{2} + a)^{2} = 12 x_{0} y_{0}^{2} .$
最後の同値は $4 y_{0}^{2} \neq = 0$ （標数が $2$ でなく $y_{0} \neq = 0$ ）を両辺に掛けた・割ったものである。 $P$ は $E$ 上の点なので $y_{0}^{2} = f (x_{0})$ 。よって最後の式は
$f^{'} (x_{0})^{2} = 12 x_{0} f (x_{0}) = 2 f (x_{0}) f^{''} (x_{0}) ⟺ 2 f (x_{0}) f^{''} (x_{0}) - f^{'} (x_{0})^{2} = 0 ⟺ ψ_{3} (x_{0}) = 0$
と同値である（ $(2)$ を使った）。

(i), (ii) と $(1)$ を合わせて、この場合も「 $P$ の位数が $3$ 」 $⟺$ $2 P = - P$ $⟺$ $x_{2} = x_{0}$ $⟺$ $ψ_{3} (x_{0}) = 0$ 。

結論. 場合 1, 2 は $y_{0}$ についての場合分けとして漏れがない。いずれの場合も同値が成り立つので、 $E (K)$ のアフィン点 $P = (x_{0}, y_{0})$ の位数が $3$ であるための必要十分条件は $ψ_{3} (x_{0}) = 3 x_{0}^{4} + 6 a x_{0}^{2} + 12 b x_{0} - a^{2} = 0$ である。 $■$

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる