モンゴメリー演算
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/19 09:53 UTC 版)
「Montgomery curve」の記事における「モンゴメリー演算」の解説
楕円曲線の点の間でいくつかの「演算」を行うことができる。2つの点 P , Q {\displaystyle P,Q} の「加算」は R = P + Q {\displaystyle R=P+Q} である3番目の点 R {\displaystyle R} を見つけることである。点の「2倍算」は、 [ 2 ] P = P + P {\displaystyle [2]P=P+P} を計算することである。（演算の詳細については、下の説明や群構造を参照のこと。） モンゴメリ形式 B y 2 = x 3 + A x 2 + x {\displaystyle By^{2}=x^{3}+Ax^{2}+x} の楕円曲線上の点 P = ( x , y ) {\displaystyle P=(x,y)} は、モンゴメリー座標 P = ( X : Z ) {\displaystyle P=(X:Z)} で表すことができる。ただし、 P = ( X : Z ) {\displaystyle P=(X:Z)} は射影座標であり、 Z ≠ 0 {\displaystyle Z\neq 0} に対して x = X / Z {\displaystyle x=X/Z} である。 注意しなければならないことは、この種の点の表現は情報を失うことである。実際、この場合、アフィン空間内の点 ( x , y ) {\displaystyle (x,y)} と ( x , − y ) {\displaystyle (x,-y)} は共に同じ点 ( X : Z ) {\displaystyle (X:Z)} で表現されるため、区別が無くなる。しかし、この表現においても、点の定数倍を得ることができる。つまり、与えられた点 P = ( X : Z ) {\displaystyle P=(X:Z)} から、 [ n ] P = ( X n : Z n ) {\displaystyle [n]P=(X_{n}:Z_{n})} を計算できる。 今、2つの点 P n = [ n ] P = ( X n : Z n ) {\displaystyle P_{n}=[n]P=(X_{n}:Z_{n})} と P m = [ m ] P = ( X m : Z m ) {\displaystyle P_{m}=[m]P=(X_{m}:Z_{m})} を考える。それらの和は点 P m + n = P m + P n = ( X m + n : Z m + n ) {\displaystyle 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 {\displaystyle 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 {\displaystyle 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 {\displaystyle m=n} ならば、演算は「2倍算」である。 [ 2 ] P n = P n + P n = P 2 n = ( X 2 n : Z 2 n ) {\displaystyle [2]P_{n}=P_{n}+P_{n}=P_{2n}=(X_{2n}:Z_{2n})} の座標は次の式で与えられる。 4 X n Z n = ( X n + Z n ) 2 − ( X n − Z n ) 2 {\displaystyle 4X_{n}Z_{n}=(X_{n}+Z_{n})^{2}-(X_{n}-Z_{n})^{2}} X 2 n = ( X n + Z n ) 2 ( X n − Z n ) 2 {\displaystyle X_{2n}=(X_{n}+Z_{n})^{2}(X_{n}-Z_{n})^{2}} Z 2 n = ( 4 X n Z n ) ( ( X n − Z n ) 2 + ( ( A + 2 ) / 4 ) ( 4 X n Z n ) ) {\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 である。定数倍の定数は ( A + 2 ) / 4 {\displaystyle (A+2)/4} であるため、D を小さくするために小さい A {\displaystyle A} を選ぶことができる。
※この「モンゴメリー演算」の解説は、「Montgomery curve」の解説の一部です。
「モンゴメリー演算」を含む「Montgomery curve」の記事については、「Montgomery curve」の概要を参照ください。
- モンゴメリー演算のページへのリンク
