モンゴメリ曲線

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

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

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

ある特定のA、B ∈ Kに対して、B ( A ² − 4) ≠ 0となります。

一般に、この曲線は、特性が2 と異なり、A ≠ ±2およびB ≠ 0である有限体 K (たとえば、 q 個の元の有限体K = F q )上_と考えられますが、 AとBに対して同じ制約を持つ有理数上も考慮されます。

楕円曲線の点の間では、いくつかの「演算」を行うことができます。2 つの点を「加算」するには、となる3 番目の点を見つけます。点を「2 倍にする」には、(演算の詳細については、群法則 を参照してください) および以下を計算します。 ${\displaystyle P,Q}$${\displaystyle R}$${\displaystyle R=P+Q}$${\displaystyle [2]P=P+P}$

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

点のこのような表現では情報が失われることに注意してください。実際、この場合、アフィン点 との間には区別がありません。なぜなら、どちらも点 によって与えられるからです。ただし、この表現では、 の倍数、つまり が与えられてを計算することが可能です。 ${\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_{mn}((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}$${\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}))}$

上で検討した最初の演算 (加算) には 3 M +2 Sの時間コストがかかります。ここで、M は楕円曲線が定義されている体の2 つの一般元間の乗算を表し、 S は体の一般元の 2 乗を表します。

2 番目の演算 (2 倍化) には 2 M  + 2 S  + 1 Dの時間コストがかかります。ここで、D は一般要素と定数の乗算を表します。定数は であるため、D を小さくするために を選択できることに 注意してください。 ${\displaystyle (A+2)/4}$${\displaystyle A}$

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

と仮定します。この実装のコストは 1M + 2S + 1*A + 3add + 1*4 です。ここで、M は必要な乗算、S は二乗、a は A による乗算を表します。 ${\displaystyle Z_{1}=1}$

${\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}=(X_{2}:Z_{2})=(9:24)}$${\displaystyle P_{2}=2P_{1}}$

アフィン座標のモンゴメリ曲線上の2つの点 が与えられると、点 は幾何学的にとを通る直線との 3 番目の交点を表します。の座標は次のようにして求めることができます。 ${\displaystyle P_{1}=(x_{1},y_{1})}$${\displaystyle P_{2}=(x_{2},y_{2})}$${\displaystyle M_{A,B}}$${\displaystyle P_{3}=P_{1}+P_{2}}$${\displaystyle M_{A,B}}$${\displaystyle P_{1}}$${\displaystyle P_{2}}$${\displaystyle (x_{3},y_{3})}$${\displaystyle P_{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) 直線を曲線と交差させ、曲線方程式の変数を に代入すると、次の 3 次方程式が得られます。 ${\displaystyle M_{A,B}}$${\displaystyle ~y}$${\displaystyle ~y=lx+m}$

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

前に述べたように、この方程式には、、および の座標に対応する 3 つの解があります。特に、この方程式は次のように書き直すことができます。 ${\displaystyle ~x}$${\displaystyle P_{1}}$${\displaystyle P_{2}}$${\displaystyle P_{3}}$

${\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 ~y}$${\displaystyle P_{3}}$${\displaystyle x_{3}}$${\displaystyle ~y=lx+m}$${\displaystyle P_{3}}$${\displaystyle ~R}$${\displaystyle R+P_{1}+P_{2}=P_{\infty }}$${\displaystyle P_{1}}$${\displaystyle P_{2}}$${\displaystyle R+P_{1}+P_{2}=P_{\infty }}$${\displaystyle -R=P_{1}+P_{2}}$${\displaystyle ~R}$${\displaystyle ~-R}$${\displaystyle ~y}$${\displaystyle ~R}$${\displaystyle ~y}$${\displaystyle x_{3}}$

まとめると、点の座標は次のようになります。 ${\displaystyle P_{3}=(x_{3},y_{3})}$${\displaystyle P_{3}=P_{1}+P_{2}}$

${\displaystyle x_{3}={\frac {B(y_{2}-y_{1})^{2}}{(x_{2}-x_{1})^{2}}}-A-x_{1}-x_{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}}$

モンゴメリ曲線上の点が与えられた場合、その点は幾何学的に曲線と に接する直線との3番目の交点を表します。したがって、点の座標を求めるには、加法の公式で示されているの と同じ方法に従うだけで十分です。ただし、この場合、直線y  =  lx  +  m はで曲線に接している必要があります。したがって、${\displaystyle P_{1}}$${\displaystyle M_{A,B}}$${\displaystyle [2]P_{1}}$${\displaystyle P_{1}}$${\displaystyle P_{3}=2P_{1}}$${\displaystyle P_{1}}$${\displaystyle M_{A,B}:f(x,y)=0}$

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

直線の 傾きを表す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}}$${\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}\\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}}}$

2とは異なる特性を持つ体を とします 。${\displaystyle K}$

モンゴメリ形式の楕円曲線を次のように します。${\displaystyle M_{A,B}}$

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

と、${\displaystyle A\in K\smallsetminus \{-2,2\}}$${\displaystyle B\in K\smallsetminus \{0\}}$

をねじれたエドワーズ形式の楕円曲線と します。${\displaystyle E_{a,d}}$

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

と${\displaystyle a,d\in K\smallsetminus \{0\},\quad a\neq d.}$

次の定理はモンゴメリ曲線とねじれエドワーズ曲線の間の双有理的同値性を示している：^[2]

定理(i) すべてのツイスト エドワーズ曲線は、 上のモンゴメリ曲線と双有理的に同値です。特に、ツイスト エドワーズ曲線は、 、およびのモンゴメリ曲線と双有理的に同値です。 ${\displaystyle K}$${\displaystyle E_{a,d}}$${\displaystyle M_{A,B}}$${\displaystyle A={\frac {2(a+d)}{a-d}}}$${\displaystyle B={\frac {4}{a-d}}}$

地図: ​

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

は次のように変形できる。方程式の各項をで割り、変数xとy をそれぞれと に代入すると、方程式が得られる。 ${\displaystyle M_{A,B}}$${\displaystyle B^{3}}$${\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}$

がモンゴメリ形式に変換できるのは、4で割り切れる位数を持ち、以下の条件を満たす場合のみである: ^[3]${\displaystyle E_{a,b}}$

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}$。

• カーブ25519
• 楕円曲線における演算コストの表– 特定のケースで必要な実行時間に関する情報

• Peter L. Montgomery (1987)。 「ポラード法と楕円曲線法による因数分解の高速化」。計算数学。48 ( 177): 243–264。doi : 10.2307/2007888。JSTOR  2007888 。
• ダニエル・J・バーンスタイン、ピーター・バークナー、マーク・ジョイ、タンジャ・ランゲ、クリスティアーネ・ピータース（2008年）。 「ツイステッド・エドワーズ・カーブ」。暗号学の進歩 – AFRICACRYPT 2008。コンピューターサイエンスの講義ノート。 Vol. 5023. シュプリンガー・フェルラーク・ベルリン・ハイデルベルク。 389–405ページ。土井：10.1007/978-3-540-68164-9_26。ISBN 978-3-540-68159-5。{{cite book}}: CS1 maint: multiple names: authors list (link)
• Wouter Castryck、Steven Galbraith、Reza Rezaeian Farashahi (2008)。「混合 Edwards-Montgomery 表現を使用した楕円曲線上の効率的な演算」(PDF)。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です

• 大きな特性を持つ体上の種数1の曲線