Pebble Coding

ソフトウェアエンジニアによるIT関連技術の備忘録

楕円曲線の自己準同型

有限体  F_p 上の楕円曲線 y^{2} = x^{3} + a x^{2} + b x + c 上の有理点(x, y)を考える。
x座標,y座標はともに0以上p(素数)未満の整数。

2つの点に対する加法を以下で定義すると、この点と加法は群をなすことが知られている。
これを点の加法と呼ぶことにする。

楕円関数の加法公式 - Pebble Coding

ここで一旦、楕円曲線を離れて、群における以下の概念を確認してみる。

G, H を群、 +_Gを群Gにおける加法、 +_Hを群Hにおける加法とする。
このとき、群Gの元a, bから群Hの元への写像 f: G \to Hが以下の関係を満たす時、写像fを準同型写像(homomorphism)という。
 f(a +_G b) = f(a) +_H f(b)

G, Hが同じ群で、加法 +_G,  +_Hも同じ演算であるときは、写像fを自己準同型写像(endomorphism)という。

楕円曲線に戻る。

楕円曲線Eの元P(x, y)から楕円曲線E'の元P'(x', y')への写像fがx,yの有理式で与えられかつ、
f(O) = Oであるとき、fを同種写像(isogeny)と呼ぶ。

楕円曲線Eから楕円曲線Fへの同種写像 fは、準同型写像であることが知られている。つまり、
 f(P +_E Q) = f(P) +_F f(Q) ここで、 +_E楕円曲線Eでの点の加法、 +_F楕円曲線Fでの点の加法を表す。

楕円曲線EからEへの同種写像は自己準同型写像となる。

すべての楕円曲線は各整数nに対して、n倍写像という自己準同型写像を持つ。
ほとんどの楕円曲線においては自己準同型写像はn倍写像だけである。
n倍写像以外に自己準同型写像を持つタイプの楕円曲線虚数乗法を持つという。

同種写像(isogeny)

楕円曲線Eの元P(x, y)から楕円曲線Fの元Q(X, Y)への写像fがx,yの有理式で与えられるとはどういうことか。

楕円曲線E  y^{2} = x^{3} + a x + bを考える。
点P(x,y)を点Q(X,Y)へ写す写像が、例えば、

 X = \frac {x^{5} + 3 x y + 3} {x^{4} y^{3} + x^{2} y + 2}
 Y = \frac {x^{3} y^{3} + 14 y + 2} {x^{7} y^{6} + x^{6} y^{3} + 89}
のようなものを考えるということである。
ただし、x, y は楕円曲線E上の点であるから、条件が与えられ、X, Y も楕円曲線F上の点であるから、
形としてはかなり限定されるであろうことが想像できる。

まず、yの2乗は x^{3} + a x + bで置き換えられるから、
xの次数の上限をなしとすれば、分母も分子もyは最大でも1次まで考えればよいことが分かる。
X, Y の式をR(x, y)で表すことにすると、一般に
 R(x, y) = \frac {p(x) + q(x) y} {r(x) + s(x) y}と書けることになる。
ここで、分母、分子に {r(x) - s(x)} {y}を掛けると、分母に出てくるyは全て2乗になるからこれもxの式で置き換えられる。
分子に出てくるyの2乗もxの式で置き換えられるから、結局、
 R(x, y) = \frac {p(x) + q(x) y} {r(x)}でよいことが分かる。

ここで、楕円曲線Eから楕円曲線Fへの同種写像は、準同型写像であるという定理を利用する。(証明はせずに使う。)
f(P) + f(-P) = f(O) = O
これは、楕円曲線E上の点Pが点Qへ写されるなら、点-Pは点-Qへ移されることを示している。

楕円曲線F上の点Qを (R_x(x, y), R_y(x,y))と書くと、
点-Qは点-Pを写したものであるから (R_x(x, -y), R_y(x, -y))と表せる。
点Qと点-Qのx座標は等しく、y座標はマイナス倍に等しいことから、
 R_x(x, y) = R_x(x, -y)
 R_y(x, y) = - R_y(x, -y)
でなければならないので、結局、
 R_x(x, y) = \frac {p(x)} {r(x)}
 R_y(x, y) = \frac {p(x) y} {r(x)}
の形であることが分かる。

Elliptic Curves: Number Theory and Cryptography, Second Edition (Discrete Mathematics and Its Applications)

Elliptic Curves: Number Theory and Cryptography, Second Edition (Discrete Mathematics and Its Applications)