Montgomery curve
最終的に、方程式
v 2 = t 3 + ( 3 − A 2 3 B 2 ) t + ( 2 A 3 − 9 A 27 B 3 ) . {\displaystyle v^{2}=t^{3}+\left({\frac {3-A^{2}}{3B^{2}}}\right)t+\left({\frac {2A^{3}-9A}{27B^{3}}}\right).}
が得られる。
したがって写像
ψ {\displaystyle \psi } : M A , B → E a , b {\displaystyle M_{A,B}\rightarrow E_{a,b}}
は次で与えられる。
( x , y ) ↦ ( t , v ) = ( x B + A 3 B , y B ) , a = 3 − A 2 3 B 2 , b = 2 A 3 − 9 A 27 B 3 {\displaystyle (x,y)\mapsto (t,v)=\left({\frac {x}{B}}+{\frac {A}{3B}},{\frac {y}{B}}\right),a={\frac {3-A^{2}}{3B^{2}}},b={\frac {2A^{3}-9A}{27B^{3}}}}
一方、体 F {\displaystyle \mathbb {F} } をベースとするワイエルシュトラス形式の楕円曲線
楕円曲線の点の間でいくつかの「演算」を行うことができる。2つの点 P , Q {\displaystyle P,Q} の「加算」は R = P + Q {\displaystyle R=P+Q} である3番目の点 R {\displaystyle R} を見つけることである。点の「2倍算」は、 [ 2 ] P = P + P {\displaystyle [2]P=P+P} を計算することである。(演算の詳細については、下の説明や群構造を参照のこと。)
モンゴメリ形式 B y 2 = x 3 + A x 2 + x {\displaystyle By^{2}=x^{3}+Ax^{2}+x} の楕円曲線上の点 P = ( x , y ) {\displaystyle P=(x,y)} は、モンゴメリー座標 P = ( X : Z ) {\displaystyle P=(X:Z)} で表すことができる。ただし、 P = ( X : Z ) {\displaystyle P=(X:Z)} は射影座標であり、 Z ≠ 0 {\displaystyle Z\neq 0} に対して x = X / Z {\displaystyle x=X/Z} である。
注意しなければならないことは、この種の点の表現は情報を失うことである。実際、この場合、アフィン空間内の点 ( x , y ) {\displaystyle (x,y)} と ( x , − y ) {\displaystyle (x,-y)} は共に同じ点 ( X : Z ) {\displaystyle (X:Z)} で表現されるため、区別が無くなる。しかし、この表現においても、点の定数倍を得ることができる。
もし m = n {\displaystyle m=n} ならば、演算は「2倍算」である。 [ 2 ] P n = P n + P n = P 2 n = ( X 2 n : Z 2 n ) {\displaystyle [2]P_{n}=P_{n}+P_{n}=P_{2n}=(X_{2n}:Z_{2n})} の座標は次の式で与えられる。
4 X n Z n = ( X n + Z n ) 2 − ( X n − Z n ) 2 {\displaystyle 4X_{n}Z_{n}=(X_{n}+Z_{n})^{2}-(X_{n}-Z_{n})^{2}}
X 2 n = ( X n + Z n ) 2 ( X n − Z n ) 2 {\displaystyle X_{2n}=(X_{n}+Z_{n})^{2}(X_{n}-Z_{n})^{2}}
Z 2 n = ( 4 X n Z n ) ( ( X n − Z n ) 2 + ( ( A + 2 ) / 4 ) ( 4 X n Z n ) ) {\displaystyle Z_{2n}=(4X_{n}Z_{n})((X_{n}-Z_{n})^{2}+((A+2)/4)(4X_{n}Z_{n}))}
楕円曲線を定義している体の要素の掛け算と二乗算の時間コストをそれぞれMとSとすると、上記の一つ目の演算(加算)の時間コストは、3M+2Sである。
また、体の要素の定数倍の時間コストをDとすると、2つ目の演算(2倍算)の時間コストは2M+2S+1D である。定数倍の定数は ( A + 2 ) / 4 {\displaystyle (A+2)/4} であるため、D を小さくするために小さい A {\displaystyle A} を選ぶことができる。