モンゴメリ曲線

数学において、モンゴメリ曲線（モンゴメリきょくせん、Montgomery curve）は楕円曲線の一つの形式であり、通常のワイエルシュトラス形式^[1]とは異なる形式である。1987年にピーターL.モンゴメリーによって導入された。特定の計算、特にさまざまな暗号化アプリケーションで使用される。

定義

方程式 ${\textstyle {\frac {1}{4}}y^{2}=x^{3}+{\frac {5}{2}}x^{2}+x}$ に対するモンゴメリ曲線

体K上のモンゴメリ曲線は次の方程式で定義される。

${\displaystyle M_{A,B}:By^{2}=x^{3}+Ax^{2}+x}$

ただし、 ${\displaystyle A}$ と ${\displaystyle B}$ は A, B ∈ KおよびB(A² − 4) ≠ 0を満たす。

一般に、この曲線は、標数が2以外の有限体K （たとえば、 要素がq個である有限体K = F_q ）上で定義される A ≠ ±2 かつ B ≠ 0 であるような曲線と考えられる。しかし、AとBの条件は同じである有理数上の曲線とも考えることもできる。

モンゴメリー演算

楕円曲線の点の間でいくつかの「演算」を行うことができる。2つの点 ${\displaystyle P,Q}$ の「加算」は ${\displaystyle R=P+Q}$ である3番目の点${\displaystyle R}$ を見つけることである。点の「2倍算」は、${\displaystyle [2]P=P+P}$ を計算することである。（演算の詳細については、下の説明や群構造を参照のこと。）

モンゴメリ形式 ${\displaystyle By^{2}=x^{3}+Ax^{2}+x}$ の楕円曲線上の点 ${\displaystyle P=(x,y)}$は、モンゴメリー座標 ${\displaystyle P=(X:Z)}$ で表すことができる。ただし、${\displaystyle P=(X:Z)}$ は射影座標であり、${\displaystyle Z\neq 0}$ に対して ${\displaystyle x=X/Z}$ である。

注意しなければならないことは、この種の点の表現は情報を失うことである。実際、この場合、アフィン空間内の点 ${\displaystyle (x,y)}$ と ${\displaystyle (x,-y)}$ は共に同じ点 ${\displaystyle (X:Z)}$ で表現されるため、区別が無くなる。しかし、この表現においても、点の定数倍を得ることができる。つまり、与えられた点 ${\displaystyle P=(X:Z)}$ から、 ${\displaystyle [n]P=(X_{n}:Z_{n})}$を計算できる。

今、2つの点 ${\displaystyle P_{n}=[n]P=(X_{n}:Z_{n})}$ と ${\displaystyle P_{m}=[m]P=(X_{m}:Z_{m})}$ を考える。それらの和は点${\displaystyle P_{m+n}=P_{m}+P_{n}=(X_{m+n}:Z_{m+n})}$ で表され、その座標は次のように与えられる。

${\displaystyle X_{m+n}=Z_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})+(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}}$

${\displaystyle Z_{m+n}=X_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})-(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}}$

もし ${\displaystyle m=n}$ ならば、演算は「2倍算」である。${\displaystyle [2]P_{n}=P_{n}+P_{n}=P_{2n}=(X_{2n}:Z_{2n})}$ の座標は次の式で与えられる。

${\displaystyle 4X_{n}Z_{n}=(X_{n}+Z_{n})^{2}-(X_{n}-Z_{n})^{2}}$

${\displaystyle X_{2n}=(X_{n}+Z_{n})^{2}(X_{n}-Z_{n})^{2}}$

${\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 である。定数倍の定数は ${\displaystyle (A+2)/4}$ であるため、D を小さくするために小さい ${\displaystyle A}$ を選ぶことができる。

アルゴリズム例

次のアルゴリズムは、モンゴメリー形式の楕円曲線上の点${\displaystyle P_{1}=(X_{1}:Z_{1})}$の2倍算を表す。

${\displaystyle Z_{1}=1}$ とする。この実装における計算コストは、1M + 2S + 1*A + 3add + 1*4である。ここで、Mは乗算、Sは二乗、"*a"は定数倍（定数aをかける）を表す。

${\displaystyle XX_{1}=X_{1}^{2}\,}$

${\displaystyle X_{2}=(XX_{1}-1)^{2}\,}$

${\displaystyle Z_{2}=4X_{1}(XX_{1}+AX_{1}+1)\,}$

計算例

${\displaystyle P_{1}=(2,{\sqrt {3}})}$を曲線 ${\displaystyle 2y^{2}=x^{3}-x^{2}+x}$ 上の点とする。 ${\displaystyle (X_{1}:Z_{1})}$座標では、${\displaystyle x_{1}=X_{1}/Z_{1}}$ より、${\displaystyle P_{1}=(2:1)}$ となる。

よって

${\displaystyle XX_{1}=X_{1}^{2}=4\,}$

${\displaystyle X_{2}=(XX_{1}-1)^{2}=9\,}$

${\displaystyle Z_{2}=4X_{1}(XX_{1}+AX_{1}+1)=24\,}$

これにより、${\displaystyle P_{2}=2P_{1}}$である点は${\displaystyle P_{2}=(X_{2}:Z_{2})=(9:24)}$である。

加算

モンゴメリ曲線 ${\displaystyle M_{A,B}}$ 上の与えられた2つの点 ${\displaystyle P_{1}=(x_{1},y_{1})}$ と ${\displaystyle P_{2}=(x_{2},y_{2})}$ に対して、点 ${\displaystyle P_{3}=P_{1}+P_{2}}$ は、幾何学的には、${\displaystyle P_{1}}$ と ${\displaystyle P_{2}}$ を通る直線と曲線 ${\displaystyle M_{A,B}}$ の3番目の交点によって決定される。${\displaystyle P_{3}}$の座標 ${\displaystyle (x_{3},y_{3})}$ は次のように計算できる。

1）アフィン平面における直線は一般に${\displaystyle ~y=lx+m}$ で表せるが、${\displaystyle P_{1}}$と${\displaystyle P_{2}}$を通るという条件から、 ${\displaystyle l={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}}$ と ${\displaystyle m=y_{1}-\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)x_{1}}$ となる。

2）この直線と曲線 ${\displaystyle M_{A,B}}$ との交点を求めるために、曲線の方程式の ${\displaystyle y}$ に ${\displaystyle y=lx+m}$ を代入する。すると次の3次方程式が得られる。

${\displaystyle x^{3}+(A-Bl^{2})x^{2}+(1-2Blm)x-Bm^{2}=0}$

この方程式には、3つの解があり、それらは ${\displaystyle P_{1}}$ と ${\displaystyle P_{2}}$ と ${\displaystyle P_{3}}$ の ${\displaystyle x}$ 座標に対応する。したがって、この方程式は次のように書き直すことができるはずである。

${\displaystyle (x-x_{1})(x-x_{2})(x-x_{3})=0}$

3）上記の2つの同じ方程式の係数、特に2次の項の係数を比較すると、次を得ることができる。

${\displaystyle -x_{1}-x_{2}-x_{3}=A-Bl^{2}}$

よって、${\displaystyle x_{3}}$ は、 ${\displaystyle x_{1}}$, ${\displaystyle y_{1}}$, ${\displaystyle x_{2}}$, ${\displaystyle y_{2}}$ によって

${\displaystyle x_{3}=B\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)^{2}-A-x_{1}-x_{2}}$

で書き表すことができる。

4）点 ${\displaystyle P_{3}}$ の ${\displaystyle y}$ 座標を見つけるためには、直線の式 ${\displaystyle y=lx+m}$ に ${\displaystyle x=x_{3}}$ を代入すれば良い。ただし、これは点 ${\displaystyle P_{3}}$ を直接与えないことに注意。この方法は、${\displaystyle R+P_{1}+P_{2}=P_{\infty }}$ を満たす点 ${\displaystyle R}$ の座標を与える。${\displaystyle R+P_{1}+P_{2}=P_{\infty }}$ が ${\displaystyle -R=P_{1}+P_{2}}$ を意味することに注意すると、${\displaystyle P_{1}+P_{2}}$ を得るためには、得られた点 ${\displaystyle R}$ から点 ${\displaystyle -R}$ を見つける必要がある。ただ、これは ${\displaystyle R}$ の ${\displaystyle y}$ の座標の符号を逆にすることで、簡単に行うことができる。つまり、直線の式に ${\displaystyle x_{3}}$ を代入して得られた ${\displaystyle y}$ 座標の符号を反転させる必要がある。

これらをまとめると、${\displaystyle P_{3}=P_{1}+P_{2}}$ である点の座標 ${\displaystyle P_{3}=(x_{3},y_{3})}$ は、次のように書ける。

${\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}}}}$

${\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}}$

2倍算

モンゴメリ曲線${\displaystyle M_{A,B}}$上の与えられた点${\displaystyle P_{1}}$に対して、点${\displaystyle P_{1}}$において曲線と接する直線を考えたとき、2倍算の点${\displaystyle [2]P_{1}}$は、直線と曲線の3番目の交点で表される。よって、点${\displaystyle P_{3}=2P_{1}}$の座標を見つけるには、加算で与えられたのと同じ方法に従えば十分である。ただし、この場合、直線${\displaystyle y=lx+m}$は点${\displaystyle P_{1}}$で曲線に接している必要がある。もし曲線${\displaystyle M_{A,B}}$が

${\displaystyle f(x,y)=x^{3}+Ax^{2}+x-By^{2}=0}$

であるならば、直線の傾きを表す${\displaystyle l}$ の値は、陰関数定理により、次の式で与えられます。

${\displaystyle l=-\left.{\frac {\partial f}{\partial x}}\right/{\frac {\partial f}{\partial y}}}$

よって、${\displaystyle l={\frac {3x_{1}^{2}+2Ax_{1}+1}{2By_{1}}}}$であり、${\displaystyle P_{3}=2P_{1}}$の座標は

${\displaystyle {\begin{aligned}x_{3}&=Bl^{2}-A-x_{1}-x_{1}={\frac {B(3x_{1}^{2}+2Ax_{1}+1)^{2}}{(2By_{1})^{2}}}-A-x_{1}-x_{1}\\&={\frac {(x_{1}^{2}-1)^{2}}{4By_{1}^{2}}}={\frac {(x_{1}^{2}-1)^{2}}{4x_{1}(x_{1}^{2}+Ax_{1}+1)}}\\[8pt]y_{3}&=(2x_{1}+x_{1}+A)l-Bl^{3}-y_{1}\\&={\frac {(2x_{1}+x_{1}+A)(3{x_{1}}^{2}+2Ax_{1}+1)}{2By_{1}}}-{\frac {B(3{x_{1}}^{2}+2Ax_{1}+1)^{3}}{(2By_{1})^{3}}}-y_{1}.\end{aligned}}}$

で求められる。

ツイステッドエドワーズ曲線との同等性

${\displaystyle K}$を、標数が2ではない体とする。

${\displaystyle M_{A,B}}$を

${\displaystyle M_{A,B}:Bv^{2}=u^{3}+Au^{2}+u}$

で表されるモンゴメリ形式の楕円曲線とする。ただし、${\displaystyle A\in K\setminus \{-2,2\}}$ 、 ${\displaystyle B\in K\setminus \{0\}}$。また、${\displaystyle E_{a,d}}$を

${\displaystyle E_{a,d}\$ :\ ax^{2}+y^{2}=1+dx^{2}y^{2},\,}

で表されるエドワーズ形式の楕円曲線とする。ただし、${\displaystyle a,d\in K\setminus \{0\},\quad a\neq d.}$。

次の定理は、モンゴメリ曲線とツイステッドエドワーズ曲線との双有理同値性を示している ^[2]。

定理（i）ツイステッドエドワーズ曲線は、${\displaystyle K}$上のモンゴメリ曲線と双有理同値である。特に、ツイステッドエドワーズ曲線${\displaystyle E_{a,d}}$は、${\displaystyle A={\frac {2(a+d)}{a-d}}}$、${\displaystyle B={\frac {4}{a-d}}}$ を満たすモンゴメリ曲線${\displaystyle M_{A,B}}$と双有理的同値である。

写像

${\displaystyle \psi \,:\,E_{a,d}\rightarrow M_{A,B}}$

${\displaystyle (x,y)\mapsto (u,v)=\left({\frac {1+y}{1-y}},{\frac {1+y}{(1-y)x}}\right)}$

は、${\displaystyle E_{a,d}}$から${\displaystyle M_{A,B}}$への双有理同値であり、逆写像：

${\displaystyle \psi ^{-1}}$ ： ${\displaystyle M_{A,B}\rightarrow E_{a,d}}$

は

${\displaystyle (u,v)\mapsto (x,y)=\left({\frac {u}{v}},{\frac {u-1}{u+1}}\right),a={\frac {A+2}{B}},d={\frac {A-2}{B}}}$

で与えられる。

2つの曲線間のこの同値性は、任意の場所で有効であるわけではないないことに注意。例えば、写像${\displaystyle \psi }$は、${\displaystyle v=0}$ や${\displaystyle u+1=0}$である${\displaystyle M_{A,B}}$ 上の点では定義されていない。

ワイエルシュトラス曲線との等価性

楕円曲線はワイエルシュトラス形式で記述できる。特に、モンゴメリ形式の楕円曲線

${\displaystyle M_{A,B}}$ ： ${\displaystyle By^{2}=x^{3}+Ax^{2}+x}$

は、次の方法で変換できる；${\displaystyle M_{A,B}}$の方程式の各項を${\displaystyle B^{3}}$で除算し、変数xとyをそれぞれ ${\displaystyle u={\frac {x}{B}}}$ と ${\displaystyle v={\frac {y}{B}}}$ に置き換える。これにより、方程式

${\displaystyle v^{2}=u^{3}+{\frac {A}{B}}u^{2}+{\frac {1}{B^{2}}}u}$

が得られる。ここから短いワイエルシュトラス形式を取得するには、uを変数 ${\displaystyle t-{\frac {A}{3B}}}$ に置き換えるだけで十分で、

${\displaystyle v^{2}=\left(t-{\frac {A}{3B}}\right)^{3}+{\frac {A}{B}}\left(t-{\frac {A}{3B}}\right)^{2}+{\frac {1}{B^{2}}}\left(t-{\frac {A}{3B}}\right);}$

最終的に、方程式

${\displaystyle v^{2}=t^{3}+\left({\frac {3-A^{2}}{3B^{2}}}\right)t+\left({\frac {2A^{3}-9A}{27B^{3}}}\right).}$

が得られる。

したがって写像

${\displaystyle \psi }$ ： ${\displaystyle M_{A,B}\rightarrow E_{a,b}}$

は次で与えられる。

${\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}}}}$

一方、体${\displaystyle \mathbb {F} }$をベースとするワイエルシュトラス形式の楕円曲線

${\displaystyle E_{a,b}}$ ： ${\displaystyle v^{2}=t^{3}+at+b}$

は、常にモンゴメリ形式に変換できるわけではない。${\displaystyle E_{a,b}}$の位数が4で割り切れ、次の条件を満たすときに、またその時に限り変換できる^[3]。

1. ${\displaystyle z^{3}+az+b=0}$ が少なくとも1つの根${\displaystyle \alpha \in \mathbb {F} }$を持ち、
2. ${\displaystyle 3\alpha ^{2}+a}$ が${\displaystyle \mathbb {F} }$において平方剰余である。

これらの条件が満たされるとき、${\displaystyle s=({\sqrt {3\alpha ^{2}+a}})^{-1}}$と置くと、写像

${\displaystyle \psi ^{-1}}$ ： ${\displaystyle E_{a,b}\rightarrow M_{A,B}}$

は

${\displaystyle (t,v)\mapsto (x,y)=\left(s(t-\alpha ),sv\right),A=3\alpha s,B=s}$

で表せる。

関連項目

• Curve25519
• 楕円曲線上の演算のコスト – 特定の場合に必要な実行時間に関する情報

脚注

1. Peter L. Montgomery (1987). “Speeding the Pollard and Elliptic Curve Methods of Factorization”. Mathematics of Computation 48 (177): 243–264. doi:10.2307/2007888. JSTOR 2007888.
2. Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters (2008). “Twisted Edwards Curves”. Progress in Cryptology – AFRICACRYPT 2008. Lecture Notes in Computer Science. 5023. Springer-Verlag Berlin Heidelberg. pp. 389–405. doi:10.1007/978-3-540-68164-9_26. ISBN 978-3-540-68159-5
3. Katsuyuki Okeya, Hiroyuki Kurumatani, and Kouichi Sakurai (2000). Elliptic Curves with the Montgomery-Form and Their Cryptographic Applications. Public Key Cryptography (PKC2000). doi:10.1007/978-3-540-46588-1_17。

参考文献

• Peter L. Montgomery (1987). “Speeding the Pollard and Elliptic Curve Methods of Factorization”. Mathematics of Computation 48 (177): 243–264. doi:10.2307/2007888. JSTOR 2007888.
• Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters (2008). “Twisted Edwards Curves”. Progress in Cryptology – AFRICACRYPT 2008. Lecture Notes in Computer Science. 5023. Springer-Verlag Berlin Heidelberg. pp. 389–405. doi:10.1007/978-3-540-68164-9_26. ISBN 978-3-540-68159-5
• Wouter Castryck; Steven Galbraith; Reza Rezaeian Farashahi (2008). Efficient Arithmetic on Elliptic Curves using a Mixed Edwards-Montgomery Representation. https://eprint.iacr.org/2008/218.pdf.

外部リンク

• 大きな標数を持つ体のGenus-1曲線