Pebble Coding

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

edward曲線における加法

ed25519

Edward曲線 x^{2} + y^{2} = a^{2} + a^{2}x^{2}y^{2}

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

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

\displaystyle Y = \frac {1} {a} \cdot \frac {y_{1} y_{2} - x_{1} x_{2}} {1 - x_{1} x_{2} y_{1} y_{2}}

この点は代数計算によって、エドワード曲線上の点になることを確かめることができる。
が、計算は長く厄介なので、計算方法を記しておく。　　

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

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

ここで、

\displaystyle a^{2}A(1 - 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}の順番で並べると、７つほどペアが消える。

B + C + D = x_{1}^{2}y_{2}^{2} + x_{2}^{2}y_{1}^{2} + x_{1}^{4}x_{2}^{2}y_{1}^{2}y_{2}^{4} + x_{1}^{2}x_{2}^{4}y_{1}^{4}y_{2}^{2} \\ + y_{1}^{2}y_{2}^{2} + x_{1}^{2}x_{2}^{2} - 4 x_{1}^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2} + x_{1}^{2}x_{2}^{2}y_{1}^{4}y_{2}^{4} + x_{1}^{4}x_{2}^{4}y_{1}^{2}y_{2}^{2} \\ - x_{1}^{2}y_{1}^{2}y_{2}^{4} - x_{2}^{2}y_{1}^{4}y_{2}^{2} - x_{1}^{4}x_{2}^{2}y_{2}^{2} - x_{1}^{2}x_{2}^{4}y_{1}^{2} \\ = 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}が２つ以上出てくるので、 x_{1}^{2} + y_{1}^{2} = a^{2} ( 1 + x_{1}^2 y_{1}^2)
x_{2}^{2} + y_{2}^{2} = a^{2} ( 1 + x_{2}^2 y_{2}^2) に置き換える。

ここで、 \frac {1} {a^{4}} (E_{4} + E_{8} + E_{12})を計算すると、５つほどペアが消え、 1 - 2 x_{1}^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2} + x_{1}^{4}x_{2}^{4}y_{1}^{4}y_{2}^{4}が残る。 あとは自明である。