Montgomery curve

数学において、モンゴメリ曲線は楕円曲線の一つの形式であり、通常のワイエルシュトラス形式とは異なる形式である。1987年にピーターL.モンゴメリーによって導入された。特定の計算、特にさまざまな暗号化アプリケーションで使用される。
定義.
体上のモンゴメリ曲線は次の方程式で定義される。
ただし、 formula_2 と formula_3 は およびを満たす。
一般に、この曲線は、標数が2以外の有限体"K" （たとえば、 要素が個である有限体 ）上で定義される かつ であるような曲線と考えられる。しかし、との条件は同じである有理数上の曲線とも考えることもできる。
モンゴメリー演算.
楕円曲線の点の間でいくつかの「演算」を行うことができる。2つの点 formula_4 の「加算」は formula_5 である3番目の点formula_6 を見つけることである。点の「2倍算」は、formula_7 を計算することである。（演算の詳細については、下の説明や群構造を参照のこと。）
モンゴメリ形式 formula_8 の楕円曲線上の点 formula_9は、モンゴメリー座標 formula_10 で表すことができる。ただし、formula_10 は射影座標であり、formula_12 に対して formula_13 である。
注意しなければならないことは、この種の点の表現は情報を失うことである。実際、この場合、アフィン空間内の点 formula_14 と formula_15 は共に同じ点 formula_16 で表現されるため、区別が無くなる。しかし、この表現においても、点の定数倍を得ることができる。つまり、与えられた点 formula_10 から、 formula_18を計算できる。
今、2つの点 formula_19 と formula_20 を考える。それらの和は点formula_21 で表され、その座標は次のように与えられる。
もし formula_24 ならば、演算は「2倍算」である。formula_25 の座標は次の式で与えられる。
楕円曲線を定義している体の要素の掛け算と二乗算の時間コストをそれぞれMとSとすると、上記の一つ目の演算（加算）の時間コストは、3M+2Sである。
また、体の要素の定数倍の時間コストをDとすると、2つ目の演算（2倍算）の時間コストは2M+2S+1D である。定数倍の定数は formula_29 であるため、D を小さくするために小さい formula_2 を選ぶことができる。
アルゴリズム例.
次のアルゴリズムは、モンゴメリー形式の楕円曲線上の点formula_31の2倍算を表す。
formula_32 とする。この実装における計算コストは、1M + 2S + 1*A + 3add + 1*4である。ここで、Mは乗算、Sは二乗、"*a"は定数倍（定数aをかける）を表す。
計算例.
formula_36を曲線 formula_37 上の点とする。 formula_38座標では、formula_39 より、formula_40 となる。
よって
これにより、formula_44である点はformula_45である。
加算.
モンゴメリ曲線 formula_46 上の与えられた2つの点 formula_47 と formula_48 に対して、点 formula_49 は、幾何学的には、formula_50 と formula_51 を通る直線と曲線 formula_46 の3番目の交点によって決定される。formula_53の座標 formula_54 は次のように計算できる。
1）アフィン平面における直線は一般にformula_55 で表せるが、formula_50とformula_51を通るという条件から、 formula_58 と formula_59 となる。
2）この直線と曲線 formula_46 との交点を求めるために、曲線の方程式の formula_61 に formula_62 を代入する。すると次の3次方程式が得られる。
この方程式には、3つの解があり、それらは formula_50 と formula_51 と formula_53 の formula_67 座標に対応する。したがって、この方程式は次のように書き直すことができるはずである。
3）上記の2つの同じ方程式の係数、特に2次の項の係数を比較すると、次を得ることができる。
よって、formula_70 は、 formula_71, formula_72, formula_73, formula_74 によって
で書き表すことができる。
4）点 formula_53 の formula_61 座標を見つけるためには、直線の式 formula_62 に formula_79 を代入すれば良い。ただし、これは点 formula_53 を直接与えないことに注意。この方法は、formula_81 を満たす点 formula_6 の座標を与える。formula_81 が formula_84 を意味することに注意すると、formula_85 を得るためには、得られた点 formula_6 から点 formula_87 を見つける必要がある。ただ、これは formula_6 の formula_61 の座標の符号を逆にすることで、簡単に行うことができる。つまり、直線の式に formula_70 を代入して得られた formula_61 座標の符号を反転させる必要がある。
これらをまとめると、formula_49 である点の座標 formula_93 は、次のように書ける。
2倍算.
モンゴメリ曲線formula_46上の与えられた点formula_50に対して、点formula_50において曲線と接する直線を考えたとき、2倍算の点formula_99は、直線と曲線の3番目の交点で表される。よって、点formula_100の座標を見つけるには、加算で与えられたのと同じ方法に従えば十分である。ただし、この場合、直線formula_62は点formula_50で曲線に接している必要がある。もし曲線formula_46が
であるならば、直線の傾きを表すformula_105 の値は、陰関数定理により、次の式で与えられます。
よって、formula_107であり、formula_100の座標は
で求められる。
ツイステッドエドワーズ曲線との同等性.
formula_110を、標数が2ではない体とする。
formula_46を
で表されるモンゴメリ形式の楕円曲線とする。ただし、formula_113 、 formula_114。また、formula_115を
で表されるエドワーズ形式の楕円曲線とする。ただし、formula_117。
次の定理は、モンゴメリ曲線とツイステッドエドワーズ曲線との双有理同値性を示している 。
定理（i）ツイステッドエドワーズ曲線は、formula_110上のモンゴメリ曲線と双有理同値である。特に、ツイステッドエドワーズ曲線formula_115は、formula_120、formula_121 を満たすモンゴメリ曲線formula_46と双有理的同値である。
写像
は、formula_115からformula_46への双有理同値であり、逆写像：
は
で与えられる。
2つの曲線間のこの同値性は、任意の場所で有効であるわけではないないことに注意。例えば、写像formula_130は、formula_131 やformula_132であるformula_46 上の点では定義されていない。
ワイエルシュトラス曲線との等価性.
楕円曲線はワイエルシュトラス形式で記述できる。特に、モンゴメリ形式の楕円曲線
は、次の方法で変換できる；formula_46の方程式の各項をformula_137で除算し"、"変数xとyをそれぞれ formula_138 と formula_139 に置き換える。これにより、方程式
が得られる。ここから短いワイエルシュトラス形式を取得するには、"u"を変数 formula_141 に置き換えるだけで十分で、
最終的に、方程式
が得られる。
したがって写像
は次で与えられる。
一方、体formula_147をベースとするワイエルシュトラス形式の楕円曲線
は、常にモンゴメリ形式に変換できるわけではない。formula_148の位数が4で割り切れ、次の条件を満たすときに、またその時に限り変換できる。
これらの条件が満たされるとき、formula_155と置くと、写像
は
で表せる。