モンゴメリ曲線のソースを表示

[[数学]]において、'''モンゴメリ曲線'''（モンゴメリきょくせん、''Montgomery curve''）は[[楕円曲線]]の一つの形式であり、通常の[[ヴァイエルシュトラスの楕円函数|ワイエルシュトラス形式]]<ref>{{Cite journal|last=[[Peter Montgomery (mathematician)|Peter L. Montgomery]]|year=1987|title=Speeding the Pollard and Elliptic Curve Methods of Factorization|journal=Mathematics of Computation|volume=48|issue=177|pages=243–264|DOI=10.2307/2007888|JSTOR=2007888}}</ref>とは異なる形式である。1987年にピーターL.モンゴメリーによって導入された。特定の計算、特にさまざまな[[楕円曲線暗号|暗号化]]アプリケーションで使用される。

== 定義 ==
[[ファイル:Montgomery_curve2.svg|右|サムネイル|300x300ピクセル|方程式 

<math display="inline">\frac{1}{4}y^2=x^3+\frac{5}{2}x^2+x</math>

に対するモンゴメリ曲線

]]
[[可換体|体]]{{Math|''K''}}上のモンゴメリ曲線は[[方程式|次の方程式]]で定義される。

: <math>M_{A,B}: By^2 = x^3 + Ax^2 + x</math>

ただし、 <math>A</math> と <math>B</math> は {{Math|''A'', ''B'' ∈ ''K''}}および{{Math|''B''(''A''<sup>2</sup> − 4) ≠ 0}}を満たす。

一般に、この[[曲線]]は、[[標数]]が2以外の[[有限体]]''K'' （たとえば、 [[元 (数学)|要素]]が{{Math|''q''}}個である有限体{{Math|1=''K'' = '''F'''<sub>''q''</sub>}} ）上で定義される {{Math|''A'' ≠ ±2}} かつ {{Math|''B'' ≠ 0}} であるような曲線と考えられる。しかし、{{Math|''A''}}と{{Math|''B''}}の条件は同じである[[有理数]]上の曲線とも考えることもできる。

== モンゴメリー演算 ==
[[点 (数学)|楕円曲線の点]]の間でいくつかの「演算」を行うことができる。2つの点 <math>P, Q</math> の「加算」は <math>R=P+Q</math> である3番目の点<math>R</math> を見つけることである。点の「2倍算」は、<math>[2]P=P+P</math> を計算することである。（演算の詳細については、下の説明や[[楕円曲線|群構造]]を参照のこと。）

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

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

今、2つの点 <math>P_n=[n]P=(X_n:Z_n)</math> と <math>P_m=[m]P=(X_m:Z_m)</math> を考える。それらの[[総和|和]]は点<math>P_{m+n}=P_m+P_n = (X_{m+n}:Z_{m+n})</math> で表され、その[[座標]]は次のように与えられる。

: <math>
X_{m+n} = Z_{m-n}((X_m-Z_m)(X_n+Z_n)+(X_m+Z_m)(X_n-Z_n))^2
</math>

: <math>
Z_{m+n} = X_{m-n}((X_m-Z_m)(X_n+Z_n)-(X_m+Z_m)(X_n-Z_n))^2
</math>

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

: <math>
4X_nZ_n = (X_n+Z_n)^2 - (X_n-Z_n)^2
</math>

: <math>
X_{2n} = (X_n+Z_n)^2(X_n-Z_n)^2
</math>

: <math>
Z_{2n} = (4X_nZ_n)((X_n-Z_n)^2+((A+2)/4)(4X_nZ_n))
</math>

楕円曲線を定義している体の要素の掛け算と二乗算の時間コストをそれぞれ'''M'''と'''S'''とすると、上記の一つ目の演算（[[楕円曲線|加算]]）の時間コストは、3'''M'''+2'''S'''である。

また、体の要素の[[定数]]倍の時間コストを'''D'''とすると、2つ目の演算（2倍算）の時間コストは'''2M'''+2'''S'''+1'''D''' である。定数倍の定数は <math>(A+2)/4</math> であるため、'''D''' を小さくするために小さい <math>A</math> を選ぶことができる。

=== アルゴリズム例 ===
次のアルゴリズムは、モンゴメリー形式の楕円曲線上の点<math>P_1=(X_1:Z_1)</math>の2倍算を表す。

<math>Z_1=1</math> とする。この実装における計算コストは、1M + 2S + 1*A + 3add + 1*4である。ここで、Mは乗算、Sは二乗、"*a"は定数倍（定数aをかける）を表す。

: <math>XX_1 = X_1^2 \, </math>

: <math>X_2 = (XX_1-1)^2 \, </math>

: <math>Z_2 = 4X_1(XX_1+AX_1+1) \, </math>

=== 計算例 ===
<math>P_1=(2,\sqrt{3})</math>を曲線 <math>2y^2 = x^3 -x^2 + x</math> 上の点とする。 <math>(X_1:Z_1)</math>座標では、<math>x_1=X_1/Z_1</math> より、<math>P_1=(2:1)</math> となる。

よって

: <math>XX_1 = X_1^2 = 4 \, </math>

: <math>X_2 = (XX_1-1)^2 = 9 \, </math>

: <math>Z_2 = 4X_1(XX_1+AX_1+1) = 24 \, </math>

これにより、<math>P_2=2P_1</math>である点は<math>P_2=(X_2:Z_2)=(9:24)</math>である。

== 加算 ==
モンゴメリ曲線 <math>M_{A,B}</math> 上の与えられた2つの点 <math>P_1=(x_1,y_1)</math> と <math>P_2=(x_2,y_2)</math> に対して、点 <math>P_3=P_1+P_2</math> は、[[幾何学|幾何学的]]には、<math>P_1</math> と <math>P_2</math> を通る直線と曲線 <math>M_{A,B}</math> の3番目の交点によって決定される。<math>P_3</math>の座標 <math>(x_3,y_3)</math> は次のように計算できる。

1）アフィン平面における直線は一般に<math>~y=lx+m</math> で表せるが、<math>P_1</math>と<math>P_2</math>を通るという条件から、 <math>l=\frac{y_2-y_1}{x_2-x_1}</math> と <math>m=y_1-\left(\frac{y_2-y_1}{x_2-x_1}\right)x_1</math> となる。

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

: <math>x^3+(A-Bl^2)x^2+(1-2Blm)x-Bm^2=0</math>

この方程式には、3つの解があり、それらは <math>P_1</math> と <math>P_2</math> と <math>P_3</math> の <math>x</math> 座標に対応する。したがって、この方程式は次のように書き直すことができるはずである。

: <math>(x-x_1)(x-x_2)(x-x_3)=0</math>

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

: <math>-x_1-x_2-x_3=A-Bl^2</math>

よって、<math>x_3</math> は、 <math>x_1</math>,  <math>y_1</math>, <math>x_2</math>, <math>y_2</math> によって

: <math>x_3 = B\left(\frac{y_2-y_1}{x_2-x_1}\right)^2-A-x_1-x_2</math>

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

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

これらをまとめると、<math>P_3=P_1+P_2</math> である点の座標 <math>P_3=(x_3,y_3)</math> は、次のように書ける。

: <math>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}</math>

: <math>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</math>

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

: <math>f(x,y)=x^3+Ax^2+x-By^2 = 0</math>

であるならば、[[傾き (数学)|直線の傾き]]を表す<math>l</math> の値は、[[陰函数定理|陰関数定理]]により、次の式で与えられます。

: <math> l=-\left.\frac{\partial f}{\partial x}\right/\frac{\partial f}{\partial y }</math>


よって、<math>l = \frac{3x_1^2 + 2Ax_1 + 1}{2By_1}</math>であり、<math>P_3=2P_1</math>の座標は

: <math>
\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}
</math>

で求められる。

== ツイステッドエドワーズ曲線との同等性 ==
<math>K</math>を、標数が2ではない体とする。

<math>M_{A,B}</math>を

: <math>M_{A,B} : Bv^2 = u^3 + Au^2 + u</math>

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

: <math>E_{a,d}\ :\ ax^2 + y^2 = 1 + dx^2y^2, \,</math>

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

次の定理は、モンゴメリ曲線とツイステッドエドワーズ曲線との[[双有理幾何学|双有理同値]]性を示している <ref>{{Cite book|last=[[Daniel J. Bernstein]], Peter Birkner, Marc Joye, [[Tanja Lange]] and Christiane Peters|title=Progress in Cryptology – AFRICACRYPT 2008|volume=5023|pages=389–405|year=2008|publisher=Springer-Verlag Berlin Heidelberg|isbn=978-3-540-68159-5|doi=10.1007/978-3-540-68164-9_26|series=Lecture Notes in Computer Science|chapter=Twisted Edwards Curves}}</ref>。

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

[[写像]]

: <math>\psi\,:\,E_{a,d} \rightarrow M_{A,B}</math>

: <math>
(x,y) \mapsto (u,v) = \left(\frac{1+y}{1-y},\frac{1+y}{(1-y)x}\right)
</math>

は、<math>E_{a,d}</math>から<math>M_{A,B}</math>への双有理同値であり、逆写像：

: <math>\psi^{-1}</math> ： <math>M_{A,B} \rightarrow E_{a,d}</math>

は

: <math>
(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}
</math>

で与えられる。

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

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

: <math>M_{A,B}</math> ： <math>By^2 = x^3 + Ax^2 + x</math>

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

: <math>v^2 = u^3 + \frac{A}{B}u^2 + \frac{1}{B^2}u </math>

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

: <math>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); </math>

最終的に、方程式

: <math>v^2 = t^3 + \left(\frac{3-A^2}{3B^2}\right)t + \left(\frac{2A^3-9A}{27B^3}\right).
 </math>

が得られる。

したがって写像

: <math>\psi</math> ： <math>M_{A,B} \rightarrow E_{a,b}</math>

は次で与えられる。

: <math>
(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}
</math>

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

: <math>E_{a,b}</math> ： <math>v^2 = t^3 + at + b</math>

は、常にモンゴメリ形式に変換できるわけではない。<math>E_{a,b}</math>の位数が4で割り切れ、次の条件を満たすときに、またその時に限り変換できる<ref>{{Cite conference|last=Katsuyuki Okeya, Hiroyuki Kurumatani, and Kouichi Sakurai|year=2000|title=Elliptic Curves with the Montgomery-Form and Their Cryptographic Applications|conference=Public Key Cryptography (PKC2000)|doi=10.1007/978-3-540-46588-1_17}}</ref>。

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

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

: <math>\psi^{-1}</math> ： <math>E_{a,b} \rightarrow M_{A,B}</math>

は

: <math>
(t,v) \mapsto (x,y) =
\left(s (t-\alpha), s v\right),
A = 3 \alpha s,
B = s
</math> 

で表せる。

== 関連項目 ==

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

== 脚注 ==
{{reflist}}

== 参考文献 ==

* {{Cite journal|last=[[Peter Montgomery (mathematician)|Peter L. Montgomery]]|year=1987|title=Speeding the Pollard and Elliptic Curve Methods of Factorization|journal=Mathematics of Computation|volume=48|issue=177|pages=243–264|DOI=10.2307/2007888|JSTOR=2007888}}
* {{Cite book|last=[[Daniel J. Bernstein]], Peter Birkner, Marc Joye, [[Tanja Lange]] and Christiane Peters|title=Progress in Cryptology – AFRICACRYPT 2008|volume=5023|pages=389–405|year=2008|publisher=[[Springer-Verlag]] Berlin Heidelberg|isbn=978-3-540-68159-5|doi=10.1007/978-3-540-68164-9_26|series=Lecture Notes in Computer Science|chapter=Twisted Edwards Curves}}
* {{Cite journal|last=Wouter Castryck|last2=Steven Galbraith|last3=Reza Rezaeian Farashahi|year=2008|title=Efficient Arithmetic on Elliptic Curves using a Mixed Edwards-Montgomery Representation|url=https://eprint.iacr.org/2008/218.pdf}}

== 外部リンク ==
* [http://hyperelliptic.org/EFD/g1p/index.html 大きな標数を持つ体のGenus-1曲線]

{{DEFAULTSORT:もんこめりきよくせん}}
[[Category:楕円曲線暗号]]
[[Category:楕円曲線]]