Montgomery curve
次のアルゴリズムは、モンゴメリー形式の楕円曲線上の点 P 1 = ( X 1 : Z 1 ) {\displaystyle P_{1}=(X_{1}:Z_{1})} の2倍算を表す。
Z 1 = 1 {\displaystyle Z_{1}=1} とする。この実装における計算コストは、1M + 2S + 1*A + 3add + 1*4である。ここで、Mは乗算、Sは二乗、"*a"は定数倍(定数aをかける)を表す。
X X 1 = X 1 2 {\displaystyle XX_{1}=X_{1}^{2}\,}
X 2 = ( X X 1 − 1 ) 2 {\displaystyle X_{2}=(XX_{1}-1)^{2}\,}
Z 2 = 4 X 1 ( X X 1 + A X 1 + 1 ) {\displaystyle Z_{2}=4X_{1}(XX_{1}+AX_{1}+1)\,}
ただ、これは R {\displaystyle R} の y {\displaystyle y} の座標の符号を逆にすることで、簡単に行うことができる。つまり、直線の式に x 3 {\displaystyle x_{3}} を代入して得られた y {\displaystyle y} 座標の符号を反転させる必要がある。
これらをまとめると、 P 3 = P 1 + P 2 {\displaystyle P_{3}=P_{1}+P_{2}} である点の座標 P 3 = ( x 3 , y 3 ) {\displaystyle P_{3}=(x_{3},y_{3})} は、次のように書ける。
x 3 = B ( y 2 − y 1 ) 2 ( x 2 − x 1 ) 2 − A − x 1 − x 2 = B ( x 2 y 1 − x 1 y 2 ) 2 x 1 x 2 ( x 2 − x 1 ) 2 {\displaystyle x_{3}={\frac {B(y_{2}-y_{1})^{2}}{(x_{2}-x_{1})^{2}}}-A-x_{1}-x_{2}={\frac {B(x_{2}y_{1}-x_{1}y_{2})^{2}}{x_{1}x_{2}(x_{2}-x_{1})^{2}}}}
y 3 = ( 2 x 1 + x 2 + A ) ( y 2 − y 1 ) x 2 − x 1 − B ( y 2 − y 1 ) 3 ( x 2 − x 1 ) 3 − y 1 {\displaystyle y_{3}={\frac {(2x_{1}+x_{2}+A)(y_{2}-y_{1})}{x_{2}-x_{1}}}-{\frac {B(y_{2}-y_{1})^{3}}{(x_{2}-x_{1})^{3}}}-y_{1}}