有限体上の楕円曲線の点の加算

$y^{2} = x^{3} + a x + b$ （ $mod p$ ）上で、傾き $λ = \frac{y _{2} - y _{1}}{x _{2} - x _{1}}$ （2 倍算では $λ = \frac{3 x _{1}^{2} + a}{2 y _{1}}$ ）を法 $p$ の逆元で計算し、 $x_{3} = λ^{2} - x_{1} - x_{2}$ , $y_{3} = λ (x_{1} - x_{3}) - y_{1}$ から $P + Q$ , $2 P$ を求められる。 $P + (- P) = O$ も扱える

前提

法 $m$ での逆元（拡張ユークリッドの互除法）（大学数学暗号理論）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

約数の見つけ方（算数整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
ユークリッドの互除法（数学A 整数の性質）
1 次不定方程式の整数解（数学A 整数の性質）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
法 $m$ での逆元（拡張ユークリッドの互除法）（大学数学暗号理論）

説明

楕円曲線 $E : y^{2} \equiv x^{3} + a x + b (mod p)$ 上の 2 点 $P, Q$ から、同じ曲線上の新しい点 $P + Q$ を計算する方法を学びます。ここで $p$ は $3$ より大きい素数、 $a, b$ は整数で、 $4 a^{3} + 27 b^{2} \neq \equiv 0 (mod p)$ とします。 $P = Q$ のときの $2 P$ （2 倍算）もこの方法で求められます。楕円曲線暗号では $2 P, 3 P, \dots$ のような点の計算を何度も行うので、この加算が基本の操作になります。

なぜそうしてよいのか

以下、合同式はすべて $mod p$ とします。 $p$ は素数なので、 $0$ でない数 $c$ は $g cd (c, p) = 1$ を満たします。よって拡張ユークリッドの互除法で逆元 $c^{- 1}$ が求まり、「 $c$ で割る」ことは「 $c^{- 1}$ を掛ける」ことと同じ意味になります。また $c d \equiv 0$ なら $c \equiv 0$ または $d \equiv 0$ です。 $p$ を法とする整数（ $0, 1, \dots, p - 1$ ）を係数とする多項式でも、因数定理が成り立ちます。つまり $f (c) \equiv 0$ なら $f (x) \equiv (x - c) g (x)$ と割り切れます。理由は、 $x^{n} - c^{n} = (x - c) (x^{n - 1} + c x^{n - 2} + \dots + c^{n - 1})$ が係数の計算だけで成り立つ恒等式だからです。 $f (x) - f (c)$ は $x^{n} - c^{n}$ の定数倍の和なので、 $x - c$ で割り切れます。

【 $P \neq = Q$ の場合】 $P = (x_{1}, y_{1})$ , $Q = (x_{2}, y_{2})$ （ $x_{1} \neq \equiv x_{2}$ ）とし、 $λ \equiv (y_{2} - y_{1}) (x_{2} - x_{1})^{- 1}$ とおきます。直線 $y = λ (x - x_{1}) + y_{1}$ は $Q$ も通ります。そこで $f (x) = x^{3} + a x + b - (λ (x - x_{1}) + y_{1})^{2}$ とおきます。 $f$ は $x^{3}$ の係数が $1$ 、 $x^{2}$ の係数が $- λ^{2}$ の 3 次式です。 $f (x_{1}) \equiv 0$ なので、因数定理より $f (x) \equiv (x - x_{1}) g (x)$ と書けます。さらに $f (x_{2}) \equiv 0$ より $(x_{2} - x_{1}) g (x_{2}) \equiv 0$ です。 $x_{2} - x_{1} \neq \equiv 0$ なので $g (x_{2}) \equiv 0$ となり、 $f (x) \equiv (x - x_{1}) (x - x_{2}) (x - x_{3})$ と書けます。 $x^{2}$ の係数を比べると $- (x_{1} + x_{2} + x_{3}) \equiv - λ^{2}$ なので、 $x_{3} \equiv λ^{2} - x_{1} - x_{2}$ です。 $f (x_{3}) \equiv 0$ なので、点 $R = (x_{3}, λ (x_{3} - x_{1}) + y_{1})$ は曲線上にあります。この $R$ の $y$ 座標の符号を反転した点 $(x_{3}, λ (x_{1} - x_{3}) - y_{1})$ を $P + Q$ と定めます。これも曲線上の点です。こう定めると、結合法則など足し算として都合のよい規則が成り立つことが知られています。

【 $P = Q$ の場合（2 倍算）】この場合は「割り算だけでできる」とは言えません。実数のときの接線の傾きは微分から出てくるからです。そこで $mod p$ で直接確かめます。多項式の微分を、係数の計算だけで定めます（ $x^{n}$ を $n x^{n - 1}$ に置き換える）。積の微分法則 $(uv)^{'} = u^{'} v + u v^{'}$ は係数どうしの恒等式なので、 $mod p$ でも成り立ちます。 $y_{1} \neq \equiv 0$ とし、 $λ \equiv (3 x_{1}^{2} + a) (2 y_{1})^{- 1}$ とおきます（ $p > 3$ なので $2 y_{1} \neq \equiv 0$ ）。上と同じ $f$ について、 $f (x_{1}) \equiv x_{1}^{3} + a x_{1} + b - y_{1}^{2} \equiv 0$ です。したがって $f (x) \equiv (x - x_{1}) g (x)$ と書け、微分すると $f^{'} (x) \equiv g (x) + (x - x_{1}) g^{'} (x)$ 、つまり $f^{'} (x_{1}) \equiv g (x_{1})$ となります。一方、 $f^{'} (x) = 3 x^{2} + a - 2 λ (λ (x - x_{1}) + y_{1})$ なので、 $f^{'} (x_{1}) \equiv 3 x_{1}^{2} + a - 2 λ y_{1} \equiv 0$ です。よって $g (x_{1}) \equiv 0$ となり、 $f (x) \equiv (x - x_{1})^{2} (x - x_{3})$ と書けます。 $x_{1}$ は重解です。 $x^{2}$ の係数を比べると $2 x_{1} + x_{3} \equiv λ^{2}$ 、つまり $x_{3} \equiv λ^{2} - 2 x_{1}$ です。これは $x_{2} = x_{1}$ とした上の式と同じ形なので、 $y_{3}$ も同じ式で求まります。

【和が無限遠点になる場合】 $x_{1} \equiv x_{2}$ なら $y_{1}^{2} \equiv y_{2}^{2}$ なので、 $(y_{1} - y_{2}) (y_{1} + y_{2}) \equiv 0$ です。よって $P = Q$ か $y_{1} + y_{2} \equiv 0$ のどちらかです。 $y_{1} + y_{2} \equiv 0$ のとき（ $2 P$ で $y_{1} \equiv 0$ の場合も含む）は、傾きの分母が $0$ になり、3 つ目の交点が得られません。このとき和を「無限遠点」と呼ぶ特別な点 $O$ と定めます。 $O$ は $0$ の役割をする点で、 $P + O = P$ です。 $P = (x, y)$ に対して $- P = (x, - y)$ と定めると、 $P + (- P) = O$ となります。

手順

特別な場合を先に確かめる。 $P = O$ なら $P + Q = Q$ 、 $Q = O$ なら $P + Q = P$ とする。 $x_{1} \equiv x_{2}$ かつ $y_{1} + y_{2} \equiv 0 (mod p)$ なら $P + Q = O$ とする（ $2 P$ で $y_{1} \equiv 0$ のときも $2 P = O$ ）。
傾き $λ$ を求める。 $P \neq = Q$ なら $λ \equiv (y_{2} - y_{1}) (x_{2} - x_{1})^{- 1}$ 、 $P = Q$ なら $λ \equiv (3 x_{1}^{2} + a) (2 y_{1})^{- 1} (mod p)$ とする。逆元は拡張ユークリッドの互除法で求める。
$x_{3} \equiv λ^{2} - x_{1} - x_{2} (mod p)$ を計算する。 $2 P$ のときは $x_{3} \equiv λ^{2} - 2 x_{1}$ とする。
$y_{3} \equiv λ (x_{1} - x_{3}) - y_{1} (mod p)$ を計算し、 $0$ 以上 $p - 1$ 以下に直す。 $(x_{3}, y_{3})$ が答えになる。
検算として、 $(x_{3}, y_{3})$ が $y^{2} \equiv x^{3} + a x + b (mod p)$ を満たすか確かめる。

例題

楕円曲線 $E : y^{2} \equiv x^{3} + 2 x + 2 (mod 17)$ 上の点 $P = (5, 1)$ について、 $2 P = (x_{3}, y_{3})$ を求めよ。ただし $0 \leq x_{3}, y_{3} \leq 16$ とする。

例題の解答

【手順1】 $y_{1} = 1 \neq \equiv 0$ なので $2 P \neq = O$ であり、公式が使える。 $P$ が曲線上にあることも確かめておく。左辺は $1^{2} = 1$ 、右辺は $125 + 10 + 2 = 137 = 17 \cdot 8 + 1 \equiv 1$ で一致する。
【手順2】 $λ \equiv (3 \cdot 5^{2} + 2) (2 \cdot 1)^{- 1} = 77 \cdot 2^{- 1}$ である。まず $77 = 17 \cdot 4 + 9$ より $77 \equiv 9$ 。次に $2^{- 1} mod 17$ を互除法で求める。 $17 = 2 \cdot 8 + 1$ より $1 = 17 - 2 \cdot 8$ なので、 $2^{- 1} \equiv - 8 \equiv 9$ である。よって $λ \equiv 9 \cdot 9 = 81 = 17 \cdot 4 + 13 \equiv 13$ 。
【手順3】2 倍算なので $x_{3} \equiv 1 3^{2} - 2 \cdot 5 = 169 - 10 = 159 = 17 \cdot 9 + 6 \equiv 6$ 。
【手順4】 $y_{3} \equiv 13 (5 - 6) - 1 = - 14 \equiv 3$ 。
【手順5】左辺は $3^{2} = 9$ 、右辺は $6^{3} + 2 \cdot 6 + 2 = 230 = 17 \cdot 13 + 9 \equiv 9$ で一致するので、 $(6, 3)$ は曲線上にある。
よって $2 P = (6, 3)$ 。

答え: $(6, 3)$

よくある誤り

傾きを普通の分数のまま扱ってしまう誤り。たとえば $λ = \frac{77}{2} = 38.5$ のように計算してしまう。正しくは分母の逆元を掛けて、 $λ \equiv 77 \cdot 2^{- 1} \equiv 9 \cdot 9 \equiv 13 (mod 17)$ とする。
3 つ目の交点 $R$ をそのまま答えにしてしまう誤り。つまり $y_{3} = λ (x_{3} - x_{1}) + y_{1}$ としてしまう。正しくは $y$ 座標の符号を反転して、 $y_{3} \equiv λ (x_{1} - x_{3}) - y_{1}$ とする。
2 倍算で $x_{3} = λ^{2} - x_{1}$ としてしまう誤り。 $x_{1}$ は $f (x) \equiv (x - x_{1})^{2} (x - x_{3})$ の重解なので、正しくは $x_{3} \equiv λ^{2} - 2 x_{1}$ である。
$x_{1} \equiv x_{2}$ かつ $y_{1} \equiv - y_{2}$ の場合や、 $y_{1} \equiv 0$ の 2 倍算で、 $(x_{2} - x_{1})^{- 1}$ や $(2 y_{1})^{- 1}$ を無理に計算しようとする誤り。 $0$ に逆元はない。正しくは $P + Q = O$ （ $2 P = O$ ）とする。

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

入口の問題

この技能を使う問題

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

楕円曲線のスカラー倍と点の位数（大学数学暗号理論）
楕円曲線の有理点群の構造（大学院数学代数幾何）