Pebble Coding

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

楕円関数の加法公式

楕円関数  {y}^{2} = {x}^{3} + a {x} + b の形式の加法公式をメモしておきます。

アフィン座標での加算公式

1) PとQが同一点の場合。
 x_3 = {\nu}^{2} - a - x_1 - x_2
 y_3 = {\nu} ( x_1 - x_3 ) - y_1
 {\nu} = \frac {3 {x_1}^{2} + 2 a x_1 + b} {2 y_1}

2)  x_1 \ne x_2の場合
 x_3 = {\lambda}^{2} - a - x_1 - x_2
 y_3 = {\lambda} (x_1 - x_3) - y_1
 {\lambda} = \frac {y_1 - y_2} {x_1 - x_2}

これをアフィン座標(affine coordinate)と呼びます。

素体  F_p 上の割り算は掛け算に比べて10倍〜50倍くらいの計算量なので、
割り算の回数を減らすように別の座標系を取ることが多いです。

点(x,y)の代わりに3つの値(X,Y,Z)を使い、2点(X', Y', Z'),(X, Y, Z)の間に、
X'=cX, Y'=cY, Z'=cZの関係がある場合、この2点を同一視する座標系を射影座標(projective coordinates)と呼びます。
(X, Y, Z)と(X/Z, Y/Z, 1)は同じ点ということになりますが、これを(x,y)と同一と考えます。

同じようにして、 X'= {c}^{2} X, Y'= {c}^{3} Y, Z'= {c} Zの関係を使って同一視した座標系をJacobian射影座標(Jacobian projective coordinates)と呼びます。

加法公式を射影座標に変換してみると、次のようになることが簡単な計算でわかります。
1) PとQが同一点の場合
 x_3 = {\nu}^{2} - a - x_1 - x_2
 y_3 = {\nu} ( x_1 - x_3 ) - y_1
 {\nu} = \frac {3 {x_1}^{2} + 2 a x_1 + b} {2 y_1}

2)  x_1 \ne x_2の場合
 x_3 = {\lambda}^{2} - a - x_1 - x_2
 y_3 = {\lambda} (x_1 - x_3) - y_1
 {\lambda} = \frac {y_1 - y_2} {x_1 - x_2}

Projective座標系での加算公式

式は単純に x_1 = X_1 / Z_1, y_1 = Y_1 / Z_1を代入すれば、得られます。
割り算を全てZ座標に集めることによって、割り算の数をProjective座標とアフィン座標の変換時のみにすることができます。

1) PとQが同一点の場合
 w = z {Z_1}^{2} + 3 {X_1}^{2}
 s = Y_1 Z_1
 B = X_1 Y_1 a
 h = {w}^{2} - 8B

 X_3 \to 2 h s
 Y_3 \to w ( 4B - h ) - 8 {Y_1}^{2} {s}^{2}
 Z_3 \to 8 {s}^{3}

2)  x_1 \ne x_2の場合
 u = Y_2 Z_1 - Y_1 Z_2
 v = X_2 Z_1 - X_1 Z_2
 A = {u}^{2} Z_1 Z_2 - {v}^{3} - 2 {v}^2 X_1 Z_2

 X_3 \to v A
 Y_3 \to u ( {v}^{2} X_1 Z_2 - A) - {v}^{3} Y_1 Z_2
 Z_3 \to {v}^{3} Z_1 Z_2

参考:

https://written.4403.biz/source/ecc_rev30r.pdf

https://link.springer.com/content/pdf/10.1007%2F3-540-49649-1_6.pdf