Montgomery curve
数学において、モンゴメリ曲線は楕円曲線の一つの形式であり、通常のワイエルシュトラス形式とは異なる形式である。1987年にピーターL.モンゴメリーによって導入された。特定の計算、特にさまざまな暗号化アプリケーションで使用される。
体K上のモンゴメリ曲線は次の方程式で定義される。
M_{A,B}: By^2 = x^3 + Ax^2 + x
ただし、 A と B は A, B ∈ KおよびB(A2 − 4) ≠ 0を満たす。
一般に、この曲線は、標数が2以外の有限体K (たとえば、 要素がq個である有限体K = Fq )上で定義される A ≠ ±2 かつ B ≠ 0 であるような曲線と考えられる。しかし、AとBの条件は同じである有理数上の曲線とも考えることもできる。
楕円曲線の点の間でいくつかの「演算」を行うことができる。2つの点 P, Q の「加算」は R=P+Q である3番目の点R を見つけることである。点の「2倍算」は、[2]P=P+P を計算することである。(演算の詳細については、下の説明や群構造を参照のこと。)
モンゴメリ形式 By^2 = x^3 + Ax^2 + x の楕円曲線上の点 P=(x,y)は、モンゴメリー座標 P=(X:Z) で表すことができる。ただし、P=(X:Z) は射影座標であり、Z\ne 0 に対して x=X/Z である。
注意しなければならないことは、この種の点の表現は情報を失うことである。実際、この場合、アフィン空間内の点 (x,y) と (x,-y) は共に同じ点 (X:Z) で表現されるため、区別が無くなる。しかし、この表現においても、点の定数倍を得ることができる。つまり、与えられた点 P=(X:Z) から、 [n]P=(X_n:Z_n)を計算できる。
今、2つの点 P_n=[n]P=(X_n:Z_n) と P_m=[m]P=(X_m:Z_m) を考える。それらの和は点P_{m+n}=P_m+P_n = (X_{m+n}:Z_{m+n}) で表され、その座標は次のように与えられる。
X_{m+n} = Z_{m-n}((X_m-Z_m)(X_n+Z_n)+(X_m+Z_m)(X_n-Z_n))^2
Z_{m+n} = X_{m-n}((X_m-Z_m)(X_n+Z_n)-(X_m+Z_m)(X_n-Z_n))^2
もし m=n ならば、演算は「2倍算」である。[2]P_n=P_n+P_n=P_{2n}=(X_{2n}:Z_{2n}) の座標は次の式で与えられる。
4X_nZ_n = (X_n+Z_n)^2 - (X_n-Z_n)^2
X_{2n} = (X_n+Z_n)^2(X_n-Z_n)^2
Z_{2n} = (4X_nZ_n)((X_n-Z_n)^2+((A+2)/4)(4X_nZ_n))
楕円曲線を定義している体の要素の掛け算と二乗算の時間コストをそれぞれMとSとすると、上記の一つ目の演算(加算)の時間コストは、3M+2Sである。
また、体の要素の定数倍の時間コストをDとすると、2つ目の演算(2倍算)の時間コストは2M+2S+1D である。定数倍の定数は (A+2)/4 であるため、D を小さくするために小さい A を選ぶことができる。
次のアルゴリズムは、モンゴメリー形式の楕円曲線上の点P_1=(X_1:Z_1)の2倍算を表す。
Z_1=1 とする。この実装における計算コストは、1M + 2S + 1*A + 3add + 1*4である。ここで、Mは乗算、Sは二乗、"*a"は定数倍(定数aをかける)を表す。
XX_1 = X_1^2 \,
X_2 = (XX_1-1)^2 \,
Z_2 = 4X_1(XX_1+AX_1+1) \,
P_1=(2,\sqrt{3})を曲線 2y^2 = x^3 -x^2 + x 上の点とする。 (X_1:Z_1)座標では、x_1=X_1/Z_1 より、P_1=(2:1) となる。
XX_1 = X_1^2 = 4 \,
X_2 = (XX_1-1)^2 = 9 \,
Z_2 = 4X_1(XX_1+AX_1+1) = 24 \,
これにより、P_2=2P_1である点はP_2=(X_2:Z_2)=(9:24)である。
モンゴメリ曲線 M_{A,B} 上の与えられた2つの点 P_1=(x_1,y_1) と P_2=(x_2,y_2) に対して、点 P_3=P_1+P_2 は、幾何学的には、P_1 と P_2 を通る直線と曲線 M_{A,B} の3番目の交点によって決定される。P_3の座標 (x_3,y_3) は次のように計算できる。
1)アフィン平面における直線は一般に~y=lx+m で表せるが、P_1とP_2を通るという条件から、 l=\frac{y_2-y_1}{x_2-x_1} と m=y_1-\left(\frac{y_2-y_1}{x_2-x_1}\right)x_1 となる。
2)この直線と曲線 M_{A,B} との交点を求めるために、曲線の方程式の y に y=lx+m を代入する。すると次の3次方程式が得られる。
x^3+(A-Bl^2)x^2+(1-2Blm)x-Bm^2=0
この方程式には、3つの解があり、それらは P_1 と P_2 と P_3 の x 座標に対応する。したがって、この方程式は次のように書き直すことができるはずである。
(x-x_1)(x-x_2)(x-x_3)=0
3)上記の2つの同じ方程式の係数、特に2次の項の係数を比較すると、次を得ることができる。
-x_1-x_2-x_3=A-Bl^2
よって、x_3 は、 x_1,  y_1, x_2, y_2 によって
x_3 = B\left(\frac{y_2-y_1}{x_2-x_1}\right)^2-A-x_1-x_2
で書き表すことができる。
4)点 P_3 の y 座標を見つけるためには、直線の式 y=lx+m に x=x_3 を代入すれば良い。ただし、これは点 P_3 を直接与えないことに注意。この方法は、R+P_1+P_2=P_\infty を満たす点 R の座標を与える。R+P_1+P_2=P_\infty が -R=P_1+P_2 を意味することに注意すると、P_1 + P_2 を得るためには、得られた点 R から点 -R を見つける必要がある。ただ、これは R の y の座標の符号を逆にすることで、簡単に行うことができる。つまり、直線の式に x_3 を代入して得られた y 座標の符号を反転させる必要がある。
これらをまとめると、P_3=P_1+P_2 である点の座標 P_3=(x_3,y_3) は、次のように書ける。
x_3 = \frac{B(y_2-y_1)^2}{(x_2-x_1)^2}-A-x_1-x_2=\frac{B(x_2y_1-x_1y_2)^2}{x_1x_2(x_2-x_1)^2}
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
モンゴメリ曲線M_{A,B}上の与えられた点P_1に対して、点P_1において曲線と接する直線を考えたとき、2倍算の点[2]P_1は、直線と曲線の3番目の交点で表される。よって、点P_3=2P_1の座標を見つけるには、加算で与えられたのと同じ方法に従えば十分である。ただし、この場合、直線y=lx+mは点P_1で曲線に接している必要がある。もし曲線M_{A,B}が
f(x,y)=x^3+Ax^2+x-By^2 = 0
であるならば、直線の傾きを表すl の値は、陰関数定理により、次の式で与えられます。
l=-\left.\frac{\partial f}{\partial x}\right/\frac{\partial f}{\partial y }
よって、l = \frac{3x_1^2 + 2Ax_1 + 1}{2By_1}であり、P_3=2P_1の座標は
\begin{align}
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{align}
で求められる。
Kを、標数が2ではない体とする。
M_{A,B}を
M_{A,B} : Bv^2 = u^3 + Au^2 + u
で表されるモンゴメリ形式の楕円曲線とする。ただし、A\in K\setminus\{-2,2\} 、 B \in K\setminus\{0\}。また、E_{a,d}を
E_{a,d}\ :\ ax^2 + y^2 = 1 + dx^2y^2, \,
で表されるエドワーズ形式の楕円曲線とする。ただし、a,d\in K\setminus\{0\}, \quad a\neq d.。
次の定理は、モンゴメリ曲線とツイステッドエドワーズ曲線との双有理同値性を示している 。
定理(i)ツイステッドエドワーズ曲線は、K上のモンゴメリ曲線と双有理同値である。特に、ツイステッドエドワーズ曲線E_{a,d}は、A = \frac{2(a+d)}{a-d}、B = \frac{4}{a-d} を満たすモンゴメリ曲線M_{A,B}と双有理的同値である。
\psi\,:\,E_{a,d} \rightarrow M_{A,B}
(x,y) \mapsto (u,v) = \left(\frac{1+y}{1-y},\frac{1+y}{(1-y)x}\right)
は、E_{a,d}からM_{A,B}への双有理同値であり、逆写像:
\psi^{-1} : M_{A,B} \rightarrow E_{a,d}
(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つの曲線間のこの同値性は、任意の場所で有効であるわけではないないことに注意。例えば、写像\psiは、v = 0 やu + 1 = 0であるM_{A,B} 上の点では定義されていない。
楕円曲線はワイエルシュトラス形式で記述できる。特に、モンゴメリ形式の楕円曲線
M_{A,B} : By^2 = x^3 + Ax^2 + x
は、次の方法で変換できる;M_{A,B}の方程式の各項をB^3で除算し、変数xとyをそれぞれ u=\frac{x}{B} と v=\frac{y}{B} に置き換える。これにより、方程式
v^2 = u^3 + \frac{A}{B}u^2 + \frac{1}{B^2}u
が得られる。ここから短いワイエルシュトラス形式を取得するには、uを変数 t-\frac{A}{3B} に置き換えるだけで十分で、
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);
最終的に、方程式
v^2 = t^3 + \left(\frac{3-A^2}{3B^2}\right)t + \left(\frac{2A^3-9A}{27B^3}\right).
が得られる。
\psi : M_{A,B} \rightarrow E_{a,b}
は次で与えられる。
(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}
一方、体\mathbb{F}をベースとするワイエルシュトラス形式の楕円曲線
E_{a,b} : v^2 = t^3 + at + b
は、常にモンゴメリ形式に変換できるわけではない。E_{a,b}の位数が4で割り切れ、次の条件を満たすときに、またその時に限り変換できる。
z^3 + az + b = 0 が少なくとも1つの根\alpha \in \mathbb{F}を持ち、
3\alpha^2 + a が\mathbb{F}において平方剰余である。
これらの条件が満たされるとき、s = (\sqrt{3\alpha^2 + a})^{-1}と置くと、写像
\psi^{-1} : E_{a,b} \rightarrow M_{A,B}
(t,v) \mapsto (x,y) =
\left(s (t-\alpha), s v\right),
A = 3 \alpha s,
B = s
で表せる。