Pebble Coding

プログラマーの作業メモ

エドワード曲線における加法

エドワード曲線 
x^{2} + y^{2} = a^{2} + a^{2}x^{2}y^{2}

において、曲線上の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}) = 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}^{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}が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})を計算すると、5つほどペアが消え、  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}が残る。 あとは簡単である。