楕円曲線のスカラー倍と点の位数

2 倍算と加算をくり返して $n P$ を求め、 $k P = O$ となる最小の $k$ （点の位数）を見つけて、 $2030 P$ のような大きなスカラー倍を $n$ を位数で割った余りに下げて求められる

前提

有限体上の楕円曲線の点の加算（大学数学暗号理論）
n 進法（数学A 整数の性質）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

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

説明

有限体上の楕円曲線の点 $P$ に対し、 $P$ を $n$ 個加えた点 $n P = P + P + \dots + P$ を $P$ のスカラー倍といいます。 $2 P, 3 P, \dots$ と順に計算すると、いつか必ず無限遠点 $O$ になります。 $k P = O$ となる最小の正の整数 $k$ を $P$ の位数といいます。位数がわかれば、 $2030 P$ のような大きな倍数を「 $2030$ を位数で割った余り」倍の点に置き換えて、少ない計算で求められます。楕円曲線暗号の鍵の計算や、群の構造を調べる場面で使います。

なぜそうしてよいのか

点の加算は、ふつうの足し算と同じ性質をもちます。交換法則 $P + Q = Q + P$ と結合法則 $(P + Q) + R = P + (Q + R)$ が成り立ち、 $O$ は $P + O = P$ をみたす「0」の役目をします（結合法則の確認は長い計算になるので、ここでは事実として使います）。この性質から、正の整数 $m, n$ に対して $m P + n P = (m + n) P$ が成り立ちます。さらに約束として $0 P = O$ と定めます。こうすると $0$ 以上の整数 $m, n$ について $m P + n P = (m + n) P$ が成り立ちます。また $- (x, y) = (x, - y)$ であり、 $- (m P) = m (- P)$ です。したがって $m P = - (n P)$ となる $m, n$ が見つかれば、 $(m + n) P = m P + n P = O$ となります。 $m P$ と $- (m P)$ は $x$ 座標が同じで $y$ 座標の符号だけが逆なので、この関係は座標の表から簡単に見つけられます。

位数が必ず存在するのは、曲線上の点が有限個しかないからです。 $P, 2 P, 3 P, \dots$ を並べると、どこかで同じ点が現れます。 $i P = j P$ （ $i < j$ ）なら、両辺に $- (i P)$ を加えて $(j - i) P = O$ です。また、 $k P = O$ がわかっているとき、 $1 \leq j \leq k - 1$ に対して $j P + (k - j) P = k P = O$ なので $j P = - ((k - j) P)$ です。 $- O = O$ なので、 $j P$ と $(k - j) P$ は一方が $O$ なら他方も $O$ です。よって $j \leq \frac{k}{2}$ の範囲で $O$ が出ないことを確かめれば、 $1 P$ から $(k - 1) P$ のすべてで $O$ が出ないといえます。

位数を $k$ とし、 $n$ を $k$ で割って $n = q k + r$ （ $0 \leq r < k$ ）と書くと、 $n P = q (k P) + r P = q O + r P = r P$ です（ $r = 0$ なら $0 P = O$ ）。合同式でいえば、 $n \equiv r (mod k)$ なら $n P = r P$ です。つまり $n P$ は $n$ そのものではなく、 $n$ を $k$ で割った余りだけで決まります。なお、位数がわからないまま大きな $n$ を計算したいときは、 $n$ を 2 進法で表し、 $n = 2 m$ なら $n P = 2 (m P)$ 、 $n = 2 m + 1$ なら $n P = 2 (m P) + P$ という 2 倍算と加算の組合せを使えば、計算回数を約 $2 lo g_{2} n$ 回に抑えられます。

手順

点 $P = (x_{1}, y_{1})$ が曲線上にあることを確かめ、2 倍算 $λ = \frac{3 x _{1}^{2} + a}{2 y _{1}}$ で $2 P$ を求める。
$k P = (k - 1) P + P$ を加算の公式でくり返し計算し、 $P, 2 P, 3 P, \dots$ の座標を表にまとめる（ $(k - 1) P$ と $P$ の $x$ 座標が等しく $y$ 座標が逆符号なら、その和は $O$ である）。
表の中から、 $x$ 座標が等しく $y$ 座標が逆符号（ $y_{1} + y_{2} \equiv 0 (mod p)$ ）の 2 点 $m P$ , $n P$ を見つける。 $m P = - (n P)$ なので $(m + n) P = O$ である。 $y$ 座標が $0$ の点 $m P$ があれば $m P = - (m P)$ なので $2 m P = O$ である。
$k = m + n$ （または $2 m$ ）とする。 $1 \leq j \leq k - 1$ では $j P = - ((k - j) P)$ なので、一方が $O$ なら他方も $O$ になる。よって $1 \leq j \leq \frac{k}{2}$ の $j P$ が $O$ でないことを表で確かめれば、位数は $k$ と確定する。
求めたい $n P$ の $n$ を $k$ で割り、余り $r$ （ $0 \leq r < k$ ）を出す。 $n \equiv r (mod k)$ なので $n P = r P$ である（ $r = 0$ なら $O$ ）。
表から $r P$ を読み取る。表にない場合は $r P = - ((k - r) P)$ を使い、 $(k - r) P$ の $y$ 座標の符号を反転させる。

例題

$F_{5}$ 上の楕円曲線 $E : y^{2} = x^{3} + x + 1 (mod 5)$ と点 $P = (0, 1)$ を考える。 $P$ の位数を求め、それを用いて $2030 P$ の座標を求めよ。

例題の解答

【手順1】 $0^{3} + 0 + 1 = 1 = 1^{2}$ なので、 $P$ は曲線上にある。 $2 P$ の傾きは $λ = \frac{3 \cdot 0 ^{2} + 1}{2 \cdot 1} = \frac{1}{2}$ である。 $2 \cdot 3 = 6 \equiv 1$ より $2^{- 1} \equiv 3$ なので $λ \equiv 3$ 。よって $x_{3} = 3^{2} - 0 - 0 = 9 \equiv 4$ 、 $y_{3} = 3 (0 - 4) - 1 = - 13 \equiv 2$ で、 $2 P = (4, 2)$ である。
【手順2】 $3 P = (4, 2) + (0, 1)$ ： $λ = \frac{1 - 2}{0 - 4} = \frac{- 1}{- 4} = \frac{1}{4}$ 。 $4 \cdot 4 = 16 \equiv 1$ より $λ \equiv 4$ 。 $x_{3} = 16 - 4 - 0 = 12 \equiv 2$ 、 $y_{3} = 4 (4 - 2) - 2 = 6 \equiv 1$ なので $3 P = (2, 1)$ 。
$4 P = (2, 1) + (0, 1)$ ： $λ = \frac{0}{- 2} = 0$ 。 $x_{3} = 0 - 2 - 0 \equiv 3$ 、 $y_{3} = 0 \cdot (2 - 3) - 1 \equiv 4$ なので $4 P = (3, 4)$ 。
$5 P = (3, 4) + (0, 1)$ ： $λ = \frac{1 - 4}{0 - 3} = 1$ 。 $x_{3} = 1 - 3 - 0 \equiv 3$ 、 $y_{3} = 1 \cdot (3 - 3) - 4 \equiv 1$ なので $5 P = (3, 1)$ 。
表： $P = (0, 1)$ , $2 P = (4, 2)$ , $3 P = (2, 1)$ , $4 P = (3, 4)$ , $5 P = (3, 1)$ 。
【手順3】 $4 P = (3, 4)$ と $5 P = (3, 1)$ は $x$ 座標が等しく、 $4 + 1 \equiv 0 (mod 5)$ である。よって $5 P = - (4 P)$ となり、 $9 P = 4 P + 5 P = O$ である。
【手順4】 $k = 9$ とする。 $1 \leq j \leq 8$ では $j P = - ((9 - j) P)$ なので、 $j \leq 4$ の $1 P, 2 P, 3 P, 4 P$ が $O$ でないことを確かめればよい。これらはすべて座標をもつ点なので $O$ ではない。したがって $8 P = - P$ , $7 P = - (2 P)$ , $6 P = - (3 P)$ , $5 P = - (4 P)$ も $O$ ではない（実際 $5 P = (3, 1)$ も座標をもつ点で $O$ ではない）。よって $P$ の位数は $9$ である。
【手順5】 $2030 = 9 \cdot 225 + 5$ なので $2030 \equiv 5 (mod 9)$ 。（ $10 \equiv 1 (mod 9)$ より $2030 = 2 \cdot 1 0^{3} + 0 \cdot 1 0^{2} + 3 \cdot 10 + 0 \equiv 2 + 0 + 3 + 0 = 5$ と、各桁の和からも確かめられる。）よって $2030 P = 5 P$ 。
【手順6】表から $5 P = (3, 1)$ と読み取れる。
答え：位数は $9$ 、 $2030 P = (3, 1)$ 。

答え: $(3, 1)$

よくある誤り

$k P = - P$ を見つけた時点で位数を $k$ としてしまう誤り。正しくは $k P + P = O$ より $(k + 1) P = O$ である。例題では $8 P = (0, 4) = - P$ なので、位数は $8$ ではなく $9$ になる。
スカラー $n$ を、法 $p$ で割った余りに下げてしまう誤り。正しくは $P$ の位数 $k$ で割る。例題で $2030 \equiv 0 (mod 5)$ として $2030 P = O$ とするのは誤りで、正しくは $2030 \equiv 5 (mod 9)$ より $2030 P = 5 P = (3, 1)$ である。
$x$ 座標が等しく $y$ 座標が逆符号の 2 点を加えるとき、傾きの式 $\frac{y _{2} - y _{1}}{x _{2} - x _{1}}$ を使って $0$ で割る計算をしてしまう誤り。 $x_{1} = x_{2}$ のときこの式は使えず、 $y_{1} + y_{2} \equiv 0 (mod p)$ なら結果は $O$ である。例： $(3, 4) + (3, 1) = O$ 。
点の逆元を $- (x, y) = (- x, - y)$ としてしまう誤り。正しくは $- (x, y) = (x, - y mod p)$ である。例： $- (4, 2) = (4, 3)$ であり、 $(1, 3)$ ではない。

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

楕円曲線のスカラー倍と点の位数

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題