Pebble Coding

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

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

ed25519

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

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

のaffine座標での加算公式その１は以下です。
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に依存しない形式その２もあり、以下です。
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に依存しない２倍算公式は、以下です。
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座標で割り算がない、効率のよい２倍算の式が得られました。
affine座標に戻すにはZの値でX,Yを割れば良いので、割り算が2回で済みます。