Pebble Coding

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

twisted edwards curve でのaffine加算公式とprojective加算公式

Twisted Edward Curveでのコンピュータでの計算の最適化手法はいくつかありますが、
この記事では、projective座標系を使って、わり算の数をへらし計算量を押さえる手法を紹介します。

twisted edwards curve
 - x^{2} + y^{2} = 1 + d x^{2} y^{2}

のaffine座標での加算公式その1は以下です。
 x_3 = \frac {x_1 y_2 + y_1 x_2} {1 + d x_1 y_1 x_2 y_2}
 y_3 = \frac {y_1 y_2 + x_1 x_2} {1 - d x_1 y_1 x_2 y_2}

式を変形しdに依存しない形式その2もあり、以下です。
 x_3 = \frac {x_1 y_1 + x_2 y_2} {y_1 y_2 - x_1 x_2}
 y_3 = \frac {x_1 y_1 - x_2 y_2} {x_1 y_2 - y_1 x_2}

こちらの式をprojective座標
 x = X/Z, y = Y/Z
に変換すると、projective座標における加算公式が得られます。

 X_3 = \frac {X_1 Y_1 {Z_2}^{2} + X_2 Y_2 {Z_1}^{2}} {Y_1 Y_2 - X_1 X_2}
 Y_3 = \frac {X_1 Y_1 {Z_2}^{2} - X_2 Y_2 {Z_1}^{2}} {X_1 Y_2 - Y_1 X_2}
 Z_3 = {Z_1 Z_2}

affine座標でのdに依存しない2倍算公式は、以下です。
 x_3 = \frac {2 x y} {y^{2} - x^{2}}
 y_3 = \frac {y^{2} + x^{2}} {2 - y^{2} + x^{2}}

これも同様に変換して、projective座標での2倍算公式が得られます。
 X_3 = \frac {2 X Y} {Y^{2} - X^{2}}
 Y_3 = \frac {Y^{2} + X^{2}} {2 Z^{2} - Y^{2} + X^{2}}
 Z_3 = 1

ここでE,G,H,Fを
 2 X Y = E
 Y^{2} - X^{2} = G
 Y^{2} + X^{2} = H
 2 Z^{2} - Y^{2} + X^{2} = F
と表しておきます。
 X_3 = \frac {E} {G}
 Y_3 = \frac {H} {F}
 Z_3 = 1
ここで、projective座標を少し回してZをFG倍してみると、
 x'_3 = E F
 y'_3 = G H
 z'_3 = F G
これでprojective座標で割り算がない、効率のよい2倍算の式が得られました。
affine座標に戻すにはZの値でX,Yを割れば良いので、割り算が2回で済みます。

プライバシーポリシー

お問い合わせ

スポンサーリンク