Pebble Coding

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

Twisted Edward曲線における加法

Twisted Edward曲線 
- x^{2} + y^{2} = 1 + d x^{2}y^{2}

において、曲線上の2つの点  (x_{1}, y_{1}), (x_{2}, y_{2}) の加算後の点を次のように定義する。

 \displaystyle X = \frac {x_{1} y_{2} + x_{2} y_{1}} {1 + d x_{1} x_{2} y_{1} y_{2}}

 \displaystyle Y = \frac {x_{1} x_{2} + y_{1} y_{2}} {1 - d x_{1} x_{2} y_{1} y_{2}}

この点は代数計算によって、Twisted Edward曲線上の点になることを確かめることができる。
が、計算は長く厄介なので、計算方法を記しておく。
計算のコツとしては常に x_{1} x_{2} y_{1} y_{2}の順序でまとめておくことである。   

 A = - X^{2} + Y^{2} - d X^{2}Y^{2}を計算し、 1に等しくなることを示す方針で行く。

代入すると  \displaystyle A = \frac {1} {(1 + d x_{1} x_{2} y_{1} y_{2})^{2}} \cdot \frac {1} {(1 - d x_{1} x_{2} y_{1} y_{2})^{2}} \cdot ( \\ - (x_{1}y_{2} + x_{2}y_{1})^{2}(1- d x_{1}x_{2}y_{1}y_{2})^{2} \\ + (x_{1}x_{2} + y_{1}y_{2})^{2} (1 + d x_{1} x_{2} y_{1} y_{2})^{2} \\ - d (x_{1}y_{2} + x_{2}y_{1})^{2} (x_{1}x_{2} + y_{1}y_{2})^{2})

ここで、

 \displaystyle A(1 - d^{2} x_{1}^{2} x_{2}^{2} y_{1}^{2} y_{2}^{2})^{2} = B + C + Dと置く。

B + C + Dを全て展開し、 x_{1}, x_{2}, y_{1}, y_{2}の順番で並べると、7つほどペアが消える。

 B + C + D = - x_{1}^{2}y_{2}^{2} - x_{2}^{2}y_{1}^{2} + x_{1}^{2} x_{2}^{2} + y_{1}^{2} y_{2}^{2} \\
- d x_{1}^{4}x_{2}^{2}y_{2}^{2} - d x_{1}^{2}x_{2}^{4}y_{1}^{2} - d x_{1}^{2}y_{1}^{2}y_{2}^{4} - d x_{2}^{2}y_{1}^{4}y_{2}^{2} + 4 d x_{1}^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2}  \\
- d^{2} x_{1}^{4}x_{2}^{2}y_{1}^{2}y_{2}^{4} - d^{2} x_{1}^{2}x_{2}^{4}y_{1}^{4}y_{2}^{2} + d^{2} x_{1}^{4}x_{2}^{4}y_{1}^{2}y_{2}^{2} + d^{2} x_{1}^{2}x_{2}^{2}y_{1}^{4}y_{2}^{4}  \\
= E_{4} + E_{8} + E_{12}

ここでE_{i}はx,yの個数を表すが、それぞれ別々に計算してゆくと、 E_{4}, E_{8}, E_{12}には、  - x_{1}^{2} + y_{1}^{2},  - x_{2}^{2} + y_{2}^{2}が2つ以上出てくるので、  - x_{1}^{2} + y_{1}^{2} = 1 + d x_{1}^2 y_{1}^2
 - x_{2}^{2} + y_{2}^{2} = 1 + d x_{2}^2 y_{2}^2 に置き換える。

ここで、   E_{4} + E_{8} + E_{12}を計算すると、  1 - 2 d^{2} x_{1}^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2} +  d^{4} x_{1}^{4}x_{2}^{4}y_{1}^{4}y_{2}^{4}が残る。 あとは自明である。

プライバシーポリシー

お問い合わせ

スポンサーリンク