数学 において、モンゴメリ曲線 （モンゴメリきょくせん、Montgomery curve ）は楕円曲線 の一つの形式であり、通常のワイエルシュトラス形式 [ 1] 暗号化 アプリケーションで使用される。
方程式
1
4
y
2
=
x
3
+
5
2
x
2
+
x
{\textstyle {\frac {1}{4}}y^{2}=x^{3}+{\frac {5}{2}}x^{2}+x}
体 K 次の方程式 で定義される。
M
A
,
B
:
B
y
2
=
x
3
+
A
x
2
+
x
{\displaystyle M_{A,B}:By^{2}=x^{3}+Ax^{2}+x}
ただし、
A
{\displaystyle A}
B
{\displaystyle B}
A , B ∈ K B (A 2 − 4) ≠ 0
一般に、この曲線 は、標数 が2以外の有限体 K （たとえば、 要素 がq K = F q A ≠ ±2B ≠ 0A B 有理数 上の曲線とも考えることもできる。
楕円曲線の点 の間でいくつかの「演算」を行うことができる。2つの点
P
,
Q
{\displaystyle P,Q}
R
=
P
+
Q
{\displaystyle R=P+Q}
R
{\displaystyle R}
[
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
]
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}
次のアルゴリズムは、モンゴメリー形式の楕円曲線上の点
P
1
=
(
X
1
:
Z
1
)
{\displaystyle P_{1}=(X_{1}:Z_{1})}
Z
1
=
1
{\displaystyle Z_{1}=1}
X
X
1
=
X
1
2
{\displaystyle XX_{1}=X_{1}^{2}\,}
X
2
=
(
X
X
1
−
1
)
2
{\displaystyle X_{2}=(XX_{1}-1)^{2}\,}
Z
2
=
4
X
1
(
X
X
1
+
A
X
1
+
1
)
{\displaystyle Z_{2}=4X_{1}(XX_{1}+AX_{1}+1)\,}
P
1
=
(
2
,
3
)
{\displaystyle P_{1}=(2,{\sqrt {3}})}
2
y
2
=
x
3
−
x
2
+
x
{\displaystyle 2y^{2}=x^{3}-x^{2}+x}
(
X
1
:
Z
1
)
{\displaystyle (X_{1}:Z_{1})}
x
1
=
X
1
/
Z
1
{\displaystyle x_{1}=X_{1}/Z_{1}}
P
1
=
(
2
:
1
)
{\displaystyle P_{1}=(2:1)}
よって
X
X
1
=
X
1
2
=
4
{\displaystyle XX_{1}=X_{1}^{2}=4\,}
X
2
=
(
X
X
1
−
1
)
2
=
9
{\displaystyle X_{2}=(XX_{1}-1)^{2}=9\,}
Z
2
=
4
X
1
(
X
X
1
+
A
X
1
+
1
)
=
24
{\displaystyle Z_{2}=4X_{1}(XX_{1}+AX_{1}+1)=24\,}
これにより、
P
2
=
2
P
1
{\displaystyle P_{2}=2P_{1}}
P
2
=
(
X
2
:
Z
2
)
=
(
9
:
24
)
{\displaystyle P_{2}=(X_{2}:Z_{2})=(9:24)}
モンゴメリ曲線
M
A
,
B
{\displaystyle M_{A,B}}
P
1
=
(
x
1
,
y
1
)
{\displaystyle P_{1}=(x_{1},y_{1})}
P
2
=
(
x
2
,
y
2
)
{\displaystyle P_{2}=(x_{2},y_{2})}
P
3
=
P
1
+
P
2
{\displaystyle P_{3}=P_{1}+P_{2}}
幾何学的 には、
P
1
{\displaystyle P_{1}}
P
2
{\displaystyle P_{2}}
M
A
,
B
{\displaystyle M_{A,B}}
P
3
{\displaystyle P_{3}}
(
x
3
,
y
3
)
{\displaystyle (x_{3},y_{3})}
1）アフィン平面における直線は一般に
y
=
l
x
+
m
{\displaystyle ~y=lx+m}
P
1
{\displaystyle P_{1}}
P
2
{\displaystyle P_{2}}
l
=
y
2
−
y
1
x
2
−
x
1
{\displaystyle l={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}}
m
=
y
1
−
(
y
2
−
y
1
x
2
−
x
1
)
x
1
{\displaystyle m=y_{1}-\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)x_{1}}
2）この直線と曲線
M
A
,
B
{\displaystyle M_{A,B}}
y
{\displaystyle y}
y
=
l
x
+
m
{\displaystyle y=lx+m}
3次方程式 が得られる。
x
3
+
(
A
−
B
l
2
)
x
2
+
(
1
−
2
B
l
m
)
x
−
B
m
2
=
0
{\displaystyle x^{3}+(A-Bl^{2})x^{2}+(1-2Blm)x-Bm^{2}=0}
この方程式には、3つの解があり、それらは
P
1
{\displaystyle P_{1}}
P
2
{\displaystyle P_{2}}
P
3
{\displaystyle P_{3}}
x
{\displaystyle x}
(
x
−
x
1
)
(
x
−
x
2
)
(
x
−
x
3
)
=
0
{\displaystyle (x-x_{1})(x-x_{2})(x-x_{3})=0}
3）上記の2つの同じ方程式の係数、特に2次の項の係数を比較すると、次を得ることができる。
−
x
1
−
x
2
−
x
3
=
A
−
B
l
2
{\displaystyle -x_{1}-x_{2}-x_{3}=A-Bl^{2}}
よって、
x
3
{\displaystyle x_{3}}
x
1
{\displaystyle x_{1}}
y
1
{\displaystyle y_{1}}
x
2
{\displaystyle x_{2}}
y
2
{\displaystyle y_{2}}
x
3
=
B
(
y
2
−
y
1
x
2
−
x
1
)
2
−
A
−
x
1
−
x
2
{\displaystyle x_{3}=B\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)^{2}-A-x_{1}-x_{2}}
で書き表すことができる。
4）点
P
3
{\displaystyle P_{3}}
y
{\displaystyle y}
y
=
l
x
+
m
{\displaystyle y=lx+m}
x
=
x
3
{\displaystyle x=x_{3}}
P
3
{\displaystyle P_{3}}
R
+
P
1
+
P
2
=
P
∞
{\displaystyle R+P_{1}+P_{2}=P_{\infty }}
R
{\displaystyle R}
R
+
P
1
+
P
2
=
P
∞
{\displaystyle R+P_{1}+P_{2}=P_{\infty }}
−
R
=
P
1
+
P
2
{\displaystyle -R=P_{1}+P_{2}}
P
1
+
P
2
{\displaystyle P_{1}+P_{2}}
R
{\displaystyle R}
−
R
{\displaystyle -R}
R
{\displaystyle R}
y
{\displaystyle y}
x
3
{\displaystyle x_{3}}
y
{\displaystyle y}
これらをまとめると、
P
3
=
P
1
+
P
2
{\displaystyle P_{3}=P_{1}+P_{2}}
P
3
=
(
x
3
,
y
3
)
{\displaystyle P_{3}=(x_{3},y_{3})}
x
3
=
B
(
y
2
−
y
1
)
2
(
x
2
−
x
1
)
2
−
A
−
x
1
−
x
2
=
B
(
x
2
y
1
−
x
1
y
2
)
2
x
1
x
2
(
x
2
−
x
1
)
2
{\displaystyle x_{3}={\frac {B(y_{2}-y_{1})^{2}}{(x_{2}-x_{1})^{2}}}-A-x_{1}-x_{2}={\frac {B(x_{2}y_{1}-x_{1}y_{2})^{2}}{x_{1}x_{2}(x_{2}-x_{1})^{2}}}}
y
3
=
(
2
x
1
+
x
2
+
A
)
(
y
2
−
y
1
)
x
2
−
x
1
−
B
(
y
2
−
y
1
)
3
(
x
2
−
x
1
)
3
−
y
1
{\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}}
モンゴメリ曲線
M
A
,
B
{\displaystyle M_{A,B}}
P
1
{\displaystyle P_{1}}
P
1
{\displaystyle P_{1}}
[
2
]
P
1
{\displaystyle [2]P_{1}}
P
3
=
2
P
1
{\displaystyle P_{3}=2P_{1}}
y
=
l
x
+
m
{\displaystyle y=lx+m}
P
1
{\displaystyle P_{1}}
M
A
,
B
{\displaystyle M_{A,B}}
f
(
x
,
y
)
=
x
3
+
A
x
2
+
x
−
B
y
2
=
0
{\displaystyle f(x,y)=x^{3}+Ax^{2}+x-By^{2}=0}
であるならば、直線の傾き を表す
l
{\displaystyle l}
陰関数定理 により、次の式で与えられます。
l
=
−
∂
f
∂
x
/
∂
f
∂
y
{\displaystyle l=-\left.{\frac {\partial f}{\partial x}}\right/{\frac {\partial f}{\partial y}}}
l
=
3
x
1
2
+
2
A
x
1
+
1
2
B
y
1
{\displaystyle l={\frac {3x_{1}^{2}+2Ax_{1}+1}{2By_{1}}}}
P
3
=
2
P
1
{\displaystyle P_{3}=2P_{1}}
x
3
=
B
l
2
−
A
−
x
1
−
x
1
=
B
(
3
x
1
2
+
2
A
x
1
+
1
)
2
(
2
B
y
1
)
2
−
A
−
x
1
−
x
1
=
(
x
1
2
−
1
)
2
4
B
y
1
2
=
(
x
1
2
−
1
)
2
4
x
1
(
x
1
2
+
A
x
1
+
1
)
y
3
=
(
2
x
1
+
x
1
+
A
)
l
−
B
l
3
−
y
1
=
(
2
x
1
+
x
1
+
A
)
(
3
x
1
2
+
2
A
x
1
+
1
)
2
B
y
1
−
B
(
3
x
1
2
+
2
A
x
1
+
1
)
3
(
2
B
y
1
)
3
−
y
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}\\&={\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{aligned}}}
で求められる。
K
{\displaystyle K}
M
A
,
B
{\displaystyle M_{A,B}}
M
A
,
B
:
B
v
2
=
u
3
+
A
u
2
+
u
{\displaystyle M_{A,B}:Bv^{2}=u^{3}+Au^{2}+u}
で表されるモンゴメリ形式の楕円曲線とする。ただし、
A
∈
K
∖
{
−
2
,
2
}
{\displaystyle A\in K\setminus \{-2,2\}}
B
∈
K
∖
{
0
}
{\displaystyle B\in K\setminus \{0\}}
E
a
,
d
{\displaystyle E_{a,d}}
E
a
,
d
:
a
x
2
+
y
2
=
1
+
d
x
2
y
2
,
{\displaystyle E_{a,d}\ :\ ax^{2}+y^{2}=1+dx^{2}y^{2},\,}
で表されるエドワーズ形式の楕円曲線とする。ただし、
a
,
d
∈
K
∖
{
0
}
,
a
≠
d
.
{\displaystyle a,d\in K\setminus \{0\},\quad a\neq d.}
次の定理は、モンゴメリ曲線とツイステッドエドワーズ曲線との双有理同値 性を示している [ 2]
定理 （i）ツイステッドエドワーズ曲線は、
K
{\displaystyle K}
E
a
,
d
{\displaystyle E_{a,d}}
A
=
2
(
a
+
d
)
a
−
d
{\displaystyle A={\frac {2(a+d)}{a-d}}}
B
=
4
a
−
d
{\displaystyle B={\frac {4}{a-d}}}
M
A
,
B
{\displaystyle M_{A,B}}
写像
ψ
:
E
a
,
d
→
M
A
,
B
{\displaystyle \psi \,:\,E_{a,d}\rightarrow M_{A,B}}
(
x
,
y
)
↦
(
u
,
v
)
=
(
1
+
y
1
−
y
,
1
+
y
(
1
−
y
)
x
)
{\displaystyle (x,y)\mapsto (u,v)=\left({\frac {1+y}{1-y}},{\frac {1+y}{(1-y)x}}\right)}
は、
E
a
,
d
{\displaystyle E_{a,d}}
M
A
,
B
{\displaystyle M_{A,B}}
ψ
−
1
{\displaystyle \psi ^{-1}}
M
A
,
B
→
E
a
,
d
{\displaystyle M_{A,B}\rightarrow E_{a,d}}
は
(
u
,
v
)
↦
(
x
,
y
)
=
(
u
v
,
u
−
1
u
+
1
)
,
a
=
A
+
2
B
,
d
=
A
−
2
B
{\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 }
v
=
0
{\displaystyle v=0}
u
+
1
=
0
{\displaystyle u+1=0}
M
A
,
B
{\displaystyle M_{A,B}}
楕円曲線はワイエルシュトラス形式で記述できる。特に、モンゴメリ形式の楕円曲線
M
A
,
B
{\displaystyle M_{A,B}}
B
y
2
=
x
3
+
A
x
2
+
x
{\displaystyle By^{2}=x^{3}+Ax^{2}+x}
は、次の方法で変換できる；
M
A
,
B
{\displaystyle M_{A,B}}
B
3
{\displaystyle B^{3}}
、 変数xとyをそれぞれ
u
=
x
B
{\displaystyle u={\frac {x}{B}}}
v
=
y
B
{\displaystyle v={\frac {y}{B}}}
v
2
=
u
3
+
A
B
u
2
+
1
B
2
u
{\displaystyle v^{2}=u^{3}+{\frac {A}{B}}u^{2}+{\frac {1}{B^{2}}}u}
が得られる。ここから短いワイエルシュトラス形式を取得するには、u を変数
t
−
A
3
B
{\displaystyle t-{\frac {A}{3B}}}
v
2
=
(
t
−
A
3
B
)
3
+
A
B
(
t
−
A
3
B
)
2
+
1
B
2
(
t
−
A
3
B
)
;
{\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);}
最終的に、方程式
v
2
=
t
3
+
(
3
−
A
2
3
B
2
)
t
+
(
2
A
3
−
9
A
27
B
3
)
.
{\displaystyle v^{2}=t^{3}+\left({\frac {3-A^{2}}{3B^{2}}}\right)t+\left({\frac {2A^{3}-9A}{27B^{3}}}\right).}
が得られる。
したがって写像
ψ
{\displaystyle \psi }
M
A
,
B
→
E
a
,
b
{\displaystyle M_{A,B}\rightarrow E_{a,b}}
は次で与えられる。
(
x
,
y
)
↦
(
t
,
v
)
=
(
x
B
+
A
3
B
,
y
B
)
,
a
=
3
−
A
2
3
B
2
,
b
=
2
A
3
−
9
A
27
B
3
{\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}}}}
一方、体
F
{\displaystyle \mathbb {F} }
E
a
,
b
{\displaystyle E_{a,b}}
v
2
=
t
3
+
a
t
+
b
{\displaystyle v^{2}=t^{3}+at+b}
は、常にモンゴメリ形式に変換できるわけではない。
E
a
,
b
{\displaystyle E_{a,b}}
[ 3]
z
3
+
a
z
+
b
=
0
{\displaystyle z^{3}+az+b=0}
α
∈
F
{\displaystyle \alpha \in \mathbb {F} }
3
α
2
+
a
{\displaystyle 3\alpha ^{2}+a}
F
{\displaystyle \mathbb {F} }
これらの条件が満たされるとき、
s
=
(
3
α
2
+
a
)
−
1
{\displaystyle s=({\sqrt {3\alpha ^{2}+a}})^{-1}}
ψ
−
1
{\displaystyle \psi ^{-1}}
E
a
,
b
→
M
A
,
B
{\displaystyle E_{a,b}\rightarrow M_{A,B}}
は
(
t
,
v
)
↦
(
x
,
y
)
=
(
s
(
t
−
α
)
,
s
v
)
,
A
=
3
α
s
,
B
=
s
{\displaystyle (t,v)\mapsto (x,y)=\left(s(t-\alpha ),sv\right),A=3\alpha s,B=s}
で表せる。
![{\displaystyle [2]P=P+P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/570ddda1b8648dbc2d668cf9d1e8128e9639b3e3)
![{\displaystyle [n]P=(X_{n}:Z_{n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb1add0c1731d3871cd989fe65009edc5632a6c1)
![{\displaystyle P_{n}=[n]P=(X_{n}:Z_{n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5866b6e03fb5cde781a46f758f418dc6ef2b816f)
![{\displaystyle P_{m}=[m]P=(X_{m}:Z_{m})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2212186b4c365f0b663153794b0bb610a85b3e0d)
![{\displaystyle [2]P_{n}=P_{n}+P_{n}=P_{2n}=(X_{2n}:Z_{2n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99e132192909e49ab2e80de93ad5441b7cfbce25)
![{\displaystyle [2]P_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3ff8cb2ed19aa7ab4e4d93ce0982a9fdadc2e83)
![{\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}\\&={\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{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ce2a17af104efe86d0db8f1b044f868fde9e710)
