ec_math.tex

\chapter{楕円曲線}
\label{chap:ec_math}
この章では暗号で使われる楕円曲線の具体的な計算式について解説します。
まず\ref{torus}節で与えたトーラスがWeierstrass（ワイエルシュトラス）の方程式と呼ばれる2変数の3次方程式で表されることを示します。
次にWeierstrassの方程式で表現された楕円曲線に対して具体的な足し算操作を導入し、群になることをみます。
更に暗号で使われているいくつかより効率のよい計算式を紹介します。

\section{トーラス上の関数}
\ref{torus}節で紹介したトーラスは長方形を一つ決めてその両端を張り付けて作りました。
複素平面上$\CC$で長方形（より一般に平行四辺形）は原点$O$と2点$\lambda_1$, $\lambda_2 \in \CC$を決めると決まります。
その長方形の頂点は$0$, $\lambda_1$, $\lambda_1+\lambda_2$,$\lambda_2$で、向かい合う辺同士を張り合わせて作ったトーラスを$T_\Lambda$と書くことにします。

さて平行四辺形を張り合わせるということは、複素平面上に同じ平行四辺形を隙間無く敷きつめたとみなせます。
平行四辺形の右端の線を越えるとぐるっと回って左端から出たのではなく、コピーされた隣の平行四辺形に飛び込んだと考えるわけです。
SFでいうところのパラレルワールドのようですね。ただしここでは本当にオリジナルと同じコピーでそれぞれは区別できないのですが。
なお敷きつめられた平行四辺形の角を格子点といい、格子点の集合を$\Lambda:=\Set{n \lambda_1 + m \lambda_2|n, m \in \ZZ}$と書きます。

ここでトーラス$T_\Lambda$上の関数$f$を考えてみましょう。
$f$を複素平面上の関数と思うと、どのコピーされた平行四辺形の上でも同じ値になります。
つまりある$z$に対して$y:=f(z)$なら$y=f(z+\lambda_1)$、$y=f(z+\lambda_2)$が成立します。
したがって任意の$z \in \CC$, $\lambda \in \Lambda$に対して
\[
f(z+ \lambda) = f(z + n \lambda_1 + m \lambda_2)= f(z).
\]
図\ref{fig:tile.pdf}で説明すると平行四辺形の中にあるどこの黒丸に対しても同じ値になるということです。
\image{tile.pdf}{トーラス$T_\Lambda$上の関数}
一般に関数$f$が、複素数$T \ne 0$と任意の$z$に対して
\[
f(z + T)=f(z)
\]
となるとき$f$は周期$T$を持つといいます。たとえば三角関数$\sin(x)$や$\cos(x)$は周期$2\pi$を持つ周期関数です。
トーラス$T_\Lambda$上の関数は$\CC$上の$\lambda_1$と$\lambda_2$の2種類の周期を持つ周期関数とみなせます。
2種類の周期を持つため2重周期関数と呼ばれます。
\section{{\altwp}関数}
トーラス$T_\Lambda$上の関数、すなわち$\lambda_1$, $\lambda_2$を周期に持つ$\CC$上の2重周期関数の例として
\[
f(z):=\sum_{\lambda \in \Lambda}\frac{1}{(z-\lambda)^3}=\sum_{n,m \in \ZZ}\frac{1}{(z-n\lambda_1-m\lambda_2)^3}
\]
があります。
無限和で一見複雑です。
ただよく見るとなるほどなと思えます。
なぜなら$f(z+\lambda_1)$を考えると$n$の代わりに$n-1$で和をとることになるのですが、全ての$n$を動くので結局は同じ値になるからです。
\[
f(z+\lambda_1)=\sum_{n,m}\frac{1}{((z+\lambda_1)-n\lambda_1-m\lambda_2)^3}=\sum_{n'=n-1,m}\frac{1}{(z-n'\lambda_1-m\lambda_2)^3}=f(z).
\]
同様に$f(z+\lambda_2)=f(z)$となるのでこの$f$は$\Lambda$についての2重周期関数です。

和をとるときに3乗分の1にしているのは$z \notin \Lambda$に対してこの和が収束するようにするためです。
$\sum_{n=1}^\infty 1/n^2$は収束しますが、$\sum_{n=1}^\infty 1/n$は収束しないのでした。
今回は$m$, $n$についての無限和なので3乗分の1になっています。
$z \in \Lambda$に対して$f(z)$は分母が0になる項を含むので無限大になります。

ちなみに同様の手法を用いて実数$\RR$上の周期関数も作れます。
たとえば
\[
g(x):=\sum_{n=-\infty}^\infty \frac{1}{(x-n)^2}
\]
とすると、これは任意の$x \in \RR \setminus \ZZ$について収束します。
そして
\[
g(x+1)=\sum_n \frac{1}{(x+1-n)^2}=\sum_n \frac{1}{(x-(n-1))^2}=\sum_{n'}\frac{1}{(x-n')^2}=g(x)
\]
が成立し、$g(x)$は周期1の周期関数です。
実は
\[
\sum_n \frac{1}{(x-n)^2}=\frac{\pi^2}{\sin^2(\pi x)}
\]
となることが知られています。

話を戻しましょう。2重周期関数には他には次の形もあります。
\[
\wp(z):=\frac{1}{z^2}+\sum_{\lambda:=n \lambda_1 + m\lambda_2 \in \Lambda \setminus \set{0}}\left(\frac{1}{(z-\lambda)^2}-\frac{1}{\lambda^2}\right).
\]
先ほどと違って2乗分の1で和をとっていますが、括弧の中で引き算をしているので$z \notin \Lambda$に対し収束することが示されます。
$n=m=0$のときは引き算する値が$1/0$の形になってしまうので取り除いて、その代わりに先頭に$1/z^2$を足しています。
この関数も先ほどと同様に$\wp(z+\lambda_i)=\wp(z)$を示すことができ、$\Lambda$についての2重周期関数であることがわかります。
この関数はWeierstrassの$\wp$（ペー）関数と呼ばれ、トーラスにとってとても重要な関数です。
$\wp$関数を微分してみましょう。
\[
\wp'(z)=-2\frac{1}{z^3}-\sum_{\lambda \in \Lambda \setminus \Set{0}}\frac{2}{(z-\lambda)^3}=-2\sum_{\lambda \in \Lambda}\frac{1}{(z-\lambda)^3}=-2f(z).
\]
先ほど定義した$f(z)$は$-(1/2)\wp'(z)$だったのでした。

\section{{\altwp}関数の関係式}
\label{wp_relation}
$\wp$関数の性質をもう少し観察してみましょう。
$\wp$の定義から$\wp(z)-1/z^2$は$z=0$で0になります。
$\wp(z)-1/z^2$を級数展開します。
級数展開とは$z=0$の付近で対象となる関数を無限個の$z$の巾乗の和で表現することです。
\[
\wp(z)-1/z^2=c_0 + c_1 z + c_2 z^2 + c_3 z^3 + \cdots.
\]
ここで$c_i$は$z$によらないある定数です（実は$\lambda_1$, $\lambda_2$から具体的に計算できます）。
今述べたように$z=0$で左辺が0なので$c_0=0$です。
次に$\wp$関数は、その定義式の形で$z$を$-z$に置き換えても同じ値になるので偶関数です。
\[
\wp(-z)=\wp(z).
\]
したがって奇数の項$c_{2i+1}$は0になります。
\[
\wp(z)=1/z^2 + c_2 z^2 + c_4 z^4 + c_6 z^6 + \cdots.
\]
よって$\wp$関数を微分すると
\[
\wp'(z)=-2/z^3 + 2 c_2 z + 4 c_4 z^3 + 6 c_6 z^5 + \cdots
\]
となります。
$\wp'(z)^2$と$4\wp(z)^3$を級数展開したものはどちらも$4/z^6$で始まります。
その差は何になるでしょうか。展開して少し頑張って計算しましょう。
\begin{align*}
\wp(z)^3&=1/z^6+3c_2/z^2+3c_4+(3c_2^2+3c_6)z^2+\cdots,\\
\wp'(z)^2&=4/z^6-8c_2/z^2-16c_4+(-24 c_6+4 c_2^2) z^2+\cdots.
\end{align*}
よって
\[
\wp'(z)^2-4\wp(z)^3=-20 c_2/z^2-28 c_4 - (36c_6 + 8c_2^2) z^2 + \cdots.
\]
$-20 c_2/z^2$の項があるので$20 c_2 \wp(z)$を足してみます。
すると
\[
\wp'(z)^2-4\wp(z)^3+20 c_2 \wp(z)=-28 c_4 +(12 c_2^2-36c_6) z^2 + \cdots.
\]
こうすると右辺は$z$の負の巾はなくなり$z$の正の巾の和だけになりました。
すると、$\wp$関数の周期性と複素解析で習うLiouville（リウビル）の定理を用いると右辺が定数であることが示されます。
つまり右辺の$z$の係数が全て消えます（たとえば$c_6=c_2^2/3$が成立する）。
よって
\[
\wp'(z)^2-4\wp(z)^3+20 c_2 \wp(z)=-28 c_4.
\]
辺を移項すると、
\begin{equation}\label{wp_eq}
\wp'(z)^2 = 4\wp(z)^3 - 20 c_2 \wp(z) - 28c_4.
\end{equation}
これは$\wp$関数が満たす非常に重要な関係式です。

$E_\Lambda:=\Set{(x,y)|y^2=4x^3-20c_2 x - 28c_4}\cup \Set{\infty}$という集合を考えます。
するとトーラス$T_\Lambda$上の点$z$に対して、
\begin{equation}\label{ec_iso}
\phi:T_\Lambda \ni z \mapsto (\wp(z), \wp'(z)) \in E_\Lambda
\end{equation}
という写像を構成できます。$\wp(z)$と$\wp'(z)$は式（\ref{wp_eq}）を満たすからです。
$z=0$は$\infty$に対応させます。
ここで証明はできませんが、この写像は1対1の関係があることが示されます。
つまりトーラス$T_\Lambda$は$E_\Lambda$という集合と同じものとみなせます。
2変数3次方程式の解の集合$E_\Lambda$を楕円曲線といいます。
以降、今まで浮輪の表面という幾何学的な描写をしていた対象物$T_\Lambda$を$\phi$を通すことによって方程式の解$E_\Lambda$という代数的なものとして扱えるようになりました。

\section{Weierstrassの方程式}
改めて用語を定義しましょう。
$k$を複素数体か標数が2でも3でもない有限体とします。
$4a^3+27b^2 \ne 0$となる$a$, $b \in k$を選びます。
\[
y^2=x^3+ax+b
\]
をWeierstrassの方程式（あるいは標準形）と呼び、
$k$上の楕円曲線$E/k$を
\[
E:=\Set{(x,y) \in \overline{k}^2|y^2=x^3+ax+b}\cup\Set{O}
\]
で定義します。
ここで$O$は無限遠点、$\overline{k}$は$k$の代数的閉包（\ref{alg_closure}節参照）です。

体$h \subseteq \overline{k}$を一つ決めます。
点$P=(x,y)\in E$について$x$, $y \in h$のとき点$P$を$h$有理点、その集合を$E(h):=\Set{(x,y) \in h^2|y^2=x^3+ax+b}\cup\Set{O}$と書きます。

今までトーラスなどのイメージしやすい複素数体上で考えていましたが、これからはコンピュータで計算しやすい有限体を念頭に置きます。
厳密には区別すべきところもあるのですが概ね同じように話を進められるため詳細には触れません。
たとえば、この章の後半で描かれる楕円曲線のグラフは$E(\RR)$を考えています。

2次元平面$(x,y)$のことをアフィン座標といいます。
アフィン座標では無限遠点を表現できません。
そのためアフィン座標を拡張した射影座標というものを導入します。
射影座標と無限遠点の正確な意味は\ref{projective}節で説明します。

\section{判別式}
Weierstrassの標準形の定義にある$4a^3+27b^2 \ne 0$という条件は3次方程式の解に関わるものです。
\begin{lemma}
3次方程式$x^3+ax+b=0$が重解を持たない必要十分条件は$4a^3+27b^2 \ne 0$です。
この関係式を3次方程式の判別式といいます。
\end{lemma}
なぜなら$x^3+ax+b=0$の3個の解を$\alpha$, $\beta$, $\gamma$とすると
\[
(x-\alpha)(x-\beta)(x-\gamma)=x^3-(\alpha+\beta+\gamma)x^2+(\alpha \beta + \beta \gamma + \gamma \alpha)x - \alpha \beta \gamma=x^3+ax+b=0.
\]
つまり解と係数の関係は
\begin{align*}
& \alpha + \beta + \gamma = 0,\\
& \alpha \beta + \beta \gamma + \gamma \alpha = a,\\
& \alpha \beta \gamma = -b.
\end{align*}
重解を持たない条件は$\alpha, \beta, \gamma$が全て異なるので$\alpha -\beta \ne 0$かつ$\beta - \gamma \ne 0$かつ$\gamma - \alpha \ne 0$。
式変形しやすいようにそれぞれ2乗して掛けると
\[
D:= (\alpha-\beta)^2(\beta-\gamma)^2(\gamma-\alpha)^2 \ne 0.
\]
これが重解を持たない条件です。
解と係数の関係を使って$D$を式変形します。
まず一つ目の式から$\alpha+\gamma=-\beta$.
二つ目の式から$\gamma \alpha=a-\beta(\alpha+\gamma)$.
これに代入して$\gamma \alpha=a+\beta^2$.
よって
\[
(\alpha-\beta)(\beta-\gamma)
 = -\beta^2 +(\alpha + \gamma) \beta - \alpha \gamma\\
 = -\beta^2 +(-\beta)(\beta) - (a + \beta^2) = -(3\beta ^2 + a).
\]
同様に$(\beta-\gamma)(\gamma-\alpha)=-(3\gamma^2+a)$, $(\gamma-\alpha)(\alpha-\beta)=-(3\alpha^2+a)$.
よって
\begin{align*}
D &= (\alpha-\beta)(\beta-\gamma) \cdot (\beta-\gamma)(\gamma-\alpha) \cdot (\gamma - \alpha)(\alpha-\beta)\\
&=  -(3\beta^2+a)(3\gamma^2+a)(3\alpha^2+a)\\
&= -\left( a^3+3(\alpha^2+\beta^2+\gamma^2)a^2+9((\alpha \beta)^2 + (\beta \gamma)^2 + (\gamma \alpha)^2)a + 27(\alpha \beta \gamma)^2 \right).
\end{align*}
ここで
\begin{align*}
& \alpha^2+\beta^2+\gamma^2
 = (\alpha+\beta+\gamma)^2-2(\alpha \beta + \beta \gamma + \gamma \alpha)
 =-2a,\\
& (\alpha \beta)^2 + (\beta \gamma)^2 + (\gamma \alpha)^2
 = (\alpha \beta + \beta \gamma + \gamma \alpha)^2-2\alpha \beta \gamma(\alpha + \beta + \gamma)=a^2
\end{align*}
を使うと
\[
-D=a^3-6a^3+9a^3+27b^2=4a^3+27b^2.
\]
つまり重解を持たない必要十分条件は$4a^3+27b^2 \ne 0$. \qed

なお、Weierstrassの方程式で制約している標数が2でも3でもないという条件は緩めることができますが、式が多少複雑になります。
ここでは省略します。

\section{楕円曲線の加法の図形的な定義}
さて、楕円曲線が暗号にとって重要なのは加法群になるからでした。
まず加法群の図形的な定義から説明しましょう。

楕円曲線$E$上に点$O$をどこでもよいので（無限遠点でなくてよい）一つ選んで固定します。
これが単位元となります。
楕円曲線$E$は3次曲線なので一般に直線とは3点で交わります。
$E$上の点$P$をとり$P$と$O$を通る直線$l_1$を考えると、それは$E$とまた別の点で交わります。
その点を点$P$の逆元$-P$と定義します。
\image{ec-neg-add.pdf}{楕円曲線上の逆元と加法}
次に$E$上の点$P$, $Q$に対しては$P$と$Q$を通る直線$l_2$が、$E$と交わるもう一つの点を$-(P+Q)$と定義します。
すなわち$P+Q$はその点$-(P+Q)$と$O$を通る直線$l_3$が、$E$と交わる更にもう一つの点です。
$P=Q$のときは$E$における接線をとります。
このようにすると楕円曲線$E$は$O$を単位元とする加法群になります。

$O$が単位元となるのを確認しましょう。
$P$と$O$を通る直線$l_1$が交わる点は$-(P+O)$です。
これは$-P$と同じ点なので$P+O=P$です。
$l_2$のとり方から交換法則$P+Q=Q+P$が成立するのはすぐわかります。

結合法則は自明ではありません。
図を描きながら様子を見ましょう。
\image{ec-op.pdf}{楕円曲線の結合法則}
楕円曲線$E$上の点$P$, $Q$, $R$, $O$を任意にとります。
$P$と$Q$を通る直線$l_1$が$E$と交わった点は$S_1:=-(P+Q)$です。
点$S_1$と$O$を通る直線$l_2$が$E$と交わった点が$S_2:=P+Q$です。
それから$S_2$と$R$を通る直線$l_3$が$E$と交わった点は$S_3:=-((P+Q)+R)$です。

同様に$Q$と$R$を通る直線$l_4$が$E$と交わった点が$S_4:=-(Q+R)$で、
点$S_4$と$O$を通る直線$l_5$が$E$と交わった点が$S_5:=Q+R$です。
最後に$S_5$と$P$を通る直線$l_6$が$E$と交わった点が$S_6:=-(P+(Q+R))$です。
結合法則は$S_3=S_6$となることです。
結合法則はWeierstrassの方程式よりも一般的な形の3次曲線
\[
x^3+c_1x^2y+c_2xy^2+c_3y^3+c_4x^2+c_5xy+c_6y^2+c_7x+c_8y+c_9=0
\]
でも成立します。
この定理は異なる2個の3次曲線は9個の点で交わるというB\'ezout（ベズー）の定理と、\index{B\'ezoutのていり@B\'ezoutの定理}
3次曲線は9個の係数を用いて表されるという事実を組み合わせて証明されます。
詳細はたとえば『楕円曲線論入門』~\cite{ec_intro}を参照ください。

ここで3次曲線の方程式が3個の1次式の積に分解できる特殊ケースを考えてみましょう。
このとき3次曲線は3本の直線$L_1$, $L_2$, $L_3$の組になります。
\image{pappus.pdf}{Pappusの定理と結合法則}
そしてその曲線、すなわち3本の直線における結合法則はPappus（パップス）の定理を意味します~\cite{pappus}。\index{Pappusのていり@Pappusの定理}
Pappusの定理とは2本の直線$L_1$, $L_3$上に点$A$, $B$, $C$, $D$, $E$, $F$をとると、
線分$AE$と$BD$、$AF$と$CD$、$BF$と$CE$のそれぞれの交点が同一直線$L_2$上にあるというものです。
Pappusの定理は中学や高校で習うMenelaus（メネラウス）の定理を使うと示せます~\cite{aozora}。
面白いですね。

\section{楕円曲線の加法公式}\label{sec:ec_add}
単位元$O$は楕円曲線$E$上のどこでもよかったのですが、特に無限遠点にとると計算が容易になります。
$y^2=x^3+ax+b$は$x$軸に対して対称なので、点$P$と無限遠点$O$を通る直線は$y$軸に平行な直線となり、$P$の逆元は$y$座標の符号を反転したものになります。
\image{ec-add.pdf}{$O$が無限遠点にあるときの楕円曲線の結合法則}
一般の点$P=(x_1,y_1)$と$Q=(x_2,y_2)$に対して点$P+Q$を図形的な定義にしたがって計算しましょう。
点$P$と$Q$を通る直線$l_2$の式は
\[
y=\frac{y_2-y_1}{x_2-x_1}(x-x_1)+y_1=\lambda (x - x_1) + y_1, \quad \text{ただし} \lambda:=\frac{y_2-y_1}{x_2-x_1}
\]
です。
直線$l_2$が点$P$, $Q$以外に交わる点を求めるために楕円曲線の定義式に代入します。
\[
\left(\lambda (x - x_1) + y_1 \right)^2=x^3+ax+b.
\]
展開すると
\[
x^3-\lambda^2 x^2 + (a+2\lambda(\lambda x_1 - y_1))x + b - (\lambda x_1 -y_1)^2=0.
\]
これが解$x=x_1$, $x_2$, $x_3$を持つので解と係数の関係で$x^2$の係数を見ると
\[
x_1 + x_2 + x_3 = \lambda^2.
\]
つまり
\begin{equation}\label{ec_add_x}
x_3=\lambda^2 - (x_1+x_2)=\left(\frac{y_2-y_1}{x_2-x_1}\right)^2-(x_1+x_2).
\end{equation}
この値を直線の式$l_2$の$x$に代入し、符号を反転させたものが$y$座標になります。

$P$と$Q$が同じ点になると、直線$l_2$は$P$における接線となります。
$y^2=x^3+ax+b$を$x$で微分すると
\[
2yy'=3x^2+a.
\]
よって$x=x_1$における傾きは
\[
y'|_{x=x_1}=\frac{3x_1^2+a}{2y_1}.
\]
よって
\[
\lambda:=\frac{3x_1^2+a}{2y_1}
\]
とおくと直線$l_2$の式は$y=\lambda(x-x_1)+y_1$となり、後は$P$, $Q$が異なる2点のときと同様にできます。
全てまとめると次のようになります。

\mydescription{
\item[単位元] 任意の$P \in E$に対して$P+O=O+P=P$。
\item[逆元] $-O:=O$。$O$でない任意の$P:=(x,y) \in E$に対して$-P:=(x,-y)$。
\item[加法] $O$でない任意の$P:=(x_1,y_1)$, $Q:=(x_2,y_2)$に対して
\label{ec_add}
\begin{align*}
x_3 &:= \lambda^2-(x_1+x_2),\\
y_3 &:= -\lambda(x_3 - x_1) - y_1.
\end{align*}
とすると$P+Q=(x_3,y_3)$。ただし
\[
\lambda :=
\begin{cases}
\dfrac{y_2-y_1}{x_2-x_1} & \text{($x_1 \ne x_2$)}, \\[3ex]
\dfrac{3x_1^2+a}{2y_1} & \text{($x_1 = x_2$)}.
\end{cases}
\]
}
加法の$\lambda$の計算で$x_1=x_2$のとき$y_1=0$にならないか心配ですが
それは$P=Q=(x_1,0)$のときです。このときは$P=-P$、つまり$P+Q=2P=O$です。

演算が計算式で与えられたので初等的な方法でも結合法則を示せそうに思えます。
ところがこれがとてもやっかいなのです。
単に計算すれば求められるはずなのですが、場合分けが多く式も複雑なため一筋縄ではいきません。
私も何度か挑戦してみましたが挫折しました。

初等的な方法でがんばって示したものとしては~\cite{elementary}がありましたので興味ある方はごらんください。
実はその文献も一番ややこしい証明の部分は
CoCoA\footnote{\url{http://cocoa.dima.unige.it/WhatIsCoCoA/WhatIsCoCoA-Japanese.html}}
という多項式を計算するための数式処理ソフトを使っていたりします。

\section{トーラスと楕円曲線の同型対応}
前節で導入した楕円曲線の加法公式とトーラス上の足し算を見直します。
トーラス上の2点$z_1$, $z_2$の足し算は$z$を複素数（あるいは2次元実数ベクトル）とみて素直に足したものでした。
\[
z_3:=z_1+z_2.
\]
\ref{wp_relation}節の式（\ref{ec_iso}）によるトーラス$T_\Lambda$から楕円曲線$E_\Lambda$への写像$\phi$を思い出します。
\begin{equation}
\phi:T_\Lambda \ni z \mapsto (\wp(z), \wp'(z)) \in E_\Lambda
\end{equation}
$P=(x_1,y_1):=\phi(z_1)=(\wp(z_1),\wp'(z_1))$, $Q=(x_2,y_2):=\phi(z_2)=(\wp(z_2),\wp'(z_2))$とすると
\[
y_i^2=4x_i^3-20c_2 x_i - 28c_4, \quad i=1, 2
\]
を満たします。
$x_i^3$の項に4がついているのを消去するために$u_i:=2x_i$, $v_i:=\sqrt{2}y_i$とすると、
\[
1/2v_i^2=1/2u_i^3-10c_2 u_i-28c_4,
\]
つまり
\[
v_i^2=u_i^3-20c_2 u_i-56c_4.
\]
点$P$と$Q$の楕円曲線上での和$R=(x_3,y_3):=P+Q$を考えると、加法公式（\ref{ec_add_x}）より
\[
u_3=\lambda^2 - (u_1+u_2)=\left(\frac{v_2-v_1}{u_2-u_1}\right)^2-(u_1+u_2).
\]
$x_i$, $y_i$の式に直すと
\[
2x_3=\frac{1}{2}\left(\frac{y_2-y_1}{x_2-x_1}\right)^2-2(x_1+x_2).
\]
もし$z_3$の$\phi$による行き先が点$R$になるなら$x_3:=\wp(z_3)=\wp(z_1+z_2)$なので、
\[
\wp(z_1+z_2)=\frac{1}{4}\left(\frac{\wp'(z_2)-\wp'(z_1)}{\wp(z_2)-\wp(z_1)}\right)^2-(\wp(z_1)+\wp(z_2)).
\]
これは実際に成立し、$\wp$関数の加法定理と呼ばれます。
加法定理は$\phi$が
\[
\phi(z_1+z_2)=\phi(z_1)+\phi(z_2)
\]
を満たすことを示しています。
左側の$+$は複素数の加算、右側の$+$は楕円曲線上の点の加算です。
つまりトーラス$T_\Lambda$と$E_\Lambda$は点が対応しているだけでなく、点の加算の構造も対応しているのです。
すごいですね。
点の足し算がそれぞれの写像の先の足し算に対応しているとき準同型写像というのでした。
$\phi$は更に1対1の対応をしているので同型写像といいます。

\section{射影空間}
\label{projective}
楕円曲線の定義には無限遠点$O$がでてきました。
これは直感的には原点からとても遠いところにある点です。
無限遠点を定義するために射影空間というものを導入します。
射影空間を使うと無限遠点の付近での挙動を扱いやすくなります。

まず実数の射影空間を紹介しましょう。
任意の$t \in \RR$に対して原点$(0,0)$を通り、傾き$t$の直線$L_t:y=tx$を考えます。
異なる$t$に対しては異なる$L_t$が対応するので
$\RR$と$\Set{L_t:t \in \RR}$は1対1の対応をしています。
$t$が大きくなるとどんどん$y$軸に近寄りますが、同じにはなりません。
$y$軸を表す直線$x=0$は$L_t$の形では表せないからです。
直線$x=0$は$t$が無限大の$L_t$に相当するといえるでしょう。
原点を通る直線の集合を$\PP^1(\RR)$と書き、実1次元射影空間といいます。
\image{p1.pdf}{原点を通る直線}
原点を通る任意の直線は原点と原点以外の点$(a,b)$を通る直線
\[
L_{(a,b)}:bx - ay = 0
\]
と表せます。
$a \ne 0$のときは$t:=b/a$とおくと$L_{(a,b)}=L_t$です。
$a = 0$のときは$b \ne 0$なので$L_{(0,b)}$は直線$x=0$になります。
$L_{(a,b)}$を使うと$L_t$と$y$軸を同じ形で表わせて都合がよいです。

ただ$L_{(a,b)}$の表し方は一意ではありません。
$L_{(2a,2b)}$も$L_{(3a,3b)}$も同じ直線を表します。
傾きが一定であれば同じ直線を表すからです。
2本の直線$L_{(a,b)}$、$L_{(c,d)}$が同じ直線を表す必要十分条件は
ある$\alpha \ne 0$があって
\begin{align*}
& a = \alpha c,\\
& b = \alpha d
\end{align*}
です。同じ直線を表す$(a,b)$の組の集合を$(a:b)$と書くことにすると
\[
\PP^1(\RR)=\Set{(a:b)|a, b \in \RR^2 \setminus \Set{(0,0)}}
\]
となります。
$(a:b)$を射影座標とか\ruby{斉次座標}{せい|じ|ざ|ひょう}といいます。
$a\ne 0$なら$(a:b)=(1:b/a)$。$a=0$なら$b \ne 0$で$(0:b)=(0:1)$です。
$\PP^1(\RR)$の元のうち、傾きが有限の直線の集合を$U_0:=\Set{(a:b)|a \ne 0}=\Set{(1:t)|t \in \RR}$とします。
$\PP^1(\RR)=U_0 \cup \Set{(0:1)}$です。
\[
\begin{array}{cccc}
\varphi_0:& U_0 & \longrightarrow & \RR \\
&\rotatebox{90}{$\in$} &             & \rotatebox{90}{$\in$} \\
&(1:t)                 & \longmapsto & t
\end{array}
\]
は1対1の対応をします。
$\varphi_0$を通すと無限遠点以外の元は通常の$\RR$の値とみなせます。
$\varphi_0:U_0 \rightarrow \RR$を$\PP^1(\RR)$の局所座標系、$t$を$(1:t) \in U_0$の局所座標といいます。

同様に$U_1:=\Set{(a:b)|b \ne 0}$とすると
$\PP^1(\RR)=U_1 \cup \Set{(1:0)}$となり、
\[
\begin{array}{cccc}
\varphi_1:& U_1 & \longrightarrow & \RR \\
&\rotatebox{90}{$\in$} &             & \rotatebox{90}{$\in$} \\
&(t:1)                 & \longmapsto & t
\end{array}
\]
が1対1の対応をします。$t=0$は$(0:1)$に対応するので無限遠点の付近を扱えます。
ただし逆に原点$(1:0)$は扱えません。

この考え方を2次元空間に適用してみましょう。
$k$を体として、2次元射影空間を
\[
\PP^2(k):=\Set{(X:Y:Z)| (X, Y, Z) \in k^3 \setminus \Set{(0, 0, 0)}}
\]
と定義します。
ここで$(X:Y:Z):=\Set{(\alpha X,\alpha Y,\alpha Z)|\alpha  \in k \setminus \Set{0}}$です。
$Z \ne 0$となる$\PP^2(k)$の部分集合$U_2=\Set{(X:Y:Z)|Z \ne 0}\subset \PP^2(k)$を考えます。
$(X:Y:Z) \in U_2$に対して$(X/Z,Y/Z) \in k^2$を対応させるとこれは$U_2$と$k^2$の1対1の対応を与えます。
\[
\begin{array}{ccccc}
\varphi_2: & U_2 & \longrightarrow & k^2 \\
&\rotatebox{90}{$\in$} &             & \rotatebox{90}{$\in$} \\
&(X:Y:Z)     & \longmapsto & (X/Z,Y/Z) \\
\varphi_2^{-1}:&(x:y:1) & \longmapsfrom & (x,y).
\end{array}
\]
逆写像は$\varphi_2^{-1}(x,y)=(x:y:1)$です。

楕円曲線の定義方程式$y^2=x^3+ax+b$を$\PP^2(k)$の中で考えると、
上記$\varphi_2$により$(Y/Z)^2=(X/Z)^3+a(X/Z)+b$,
つまり
\[
Y^2Z = X^3 + aXZ^2 + bZ^3
\]
となります。
この式で$Z=0$とすると$X^3=0$、つまり$X=0$。
したがって$(X:Y:Z)=(0:Y:0)=(0:1:0)$はこの定義方程式をみたします。
これが無限遠点$O$の正体です。
つまり、$\Set{(x,y) \in k^2|y^2=x^3+ax+b}$に無限遠点$O$を追加した集合は
\[
\Set{(X:Y:Z) \in \PP^2(k) |Y^2Z=X^3+aXZ^2+bZ^3}
\]
という一つの式で与えられることがわかりました。

括弧の中の$Y^2Z=X^3+aXZ^2+bZ^3$という式はどの項も3次です。
$Y^2Z$は$Y$について2次、$Z$について1次、合計3次。$XZ^2$, $Z^3$も3次。
このように、どの項も同じ次数である多項式を同次多項式、あるいは斉次多項式といいます。
$(X:Y:Z)$を斉次座標というのはこれが由来です。
\section{射影座標での加法公式}
射影空間のメリットは楕円曲線の無限遠点をきちんと定義するだけではありません。
通常のアフィン座標での加法に比べて射影座標での加法は効率がよくなることがあります。
コンピュータで楕円曲線暗号を扱うときはたくさんの加法を行うので効率のよい加法公式は重要です。

有限体上の四則計算のうち一番処理が大変なのは除算です。
加減算の演算コストは一番軽いです。
パラメータや処理するコンピュータに強く依存しますが乗算は足し算の十数倍から数十倍、除算は乗算の数十倍から百倍以上のコストがかかります。

したがって除算をできるだけ回避できる公式が望ましいのです。
アフィン座標で定義された加法公式（\ref{ec_add_x}）では直線の傾きを求めるところに除算があります。
射影座標を使うことで傾きを整数の比のままで扱い、除算をしないように書き直してみましょう。

$(x_1,y_1):=(X_1/Z_1,Y_1/Z_1)$, $(x_2,y_2):=(X_2/Z_2,Y_2/Z_2)$とします。
まず2点を通る直線の傾き$\lambda$を求めます。
2点が異なるときは$\lambda:=(y_2-y_1)/(x_2-x_1)$だったので
\[
\lambda = \frac{y_2-y_1}{x_2-x_1}=\frac{Y_2/Z_2-Y_1/Z_1}{X_2/Z_2-X_1/Z_1}=\frac{Y_2Z_1-Y_1Z_2}{X_2Z_1-X_1Z_2}.
\]
この分子と分母を$u:=Y_2Z_1-Y_1Z_2$, $v:=X_2Z_1-X_1Z_2$とします。
2点$(x_1,y_1)$と$(x_2,y_2)$が通る直線が楕円曲線と通る残りの点を$(x_3,y_3)$とすると
\[
x_3:=\lambda^2 - (x_1+x_2)=u^2/v^2-(X_1/Z_1+X_2/Z_2)=(u/v)^2-\frac{X_1Z_2+X_2Z_1}{Z_1 Z_2}.
\]
$X_1Z_2+X_2Z_1 = v + 2X_1 Z_2$なので両辺に$v^2 Z_1 Z_2$を掛けると
\[
x_3 (v^2Z_1 Z_2)=u^2 Z_1 Z_2 - v^2(v + 2X_1 Z_2).
\]
右辺を$w$とおくと
\[
x_3=\frac{w}{v^2 Z_1 Z_2}.
\]
次に$y_3$を考えます。
\[
y_3:=-\lambda(x_3-x_1)-y_1=-(u/v)\left(\frac{w}{v^2 Z_1 Z_2} - x_1\right)-y_1.
\]
両辺に$v^3 Z_1 Z_2$を掛けると
\begin{align*}
y_3 (v^3 Z_1 Z_2) &= -u(w-v^2 Z_1 Z_2 (X_1/Z_1)) - v^3 Z_1 Z_2 (Y_1/Z_1)\\
&=u(v^2X_1 Z_2-w)-v^3Y_1 Z_2.
\end{align*}
$(x_3,y_3)=(X_3/Z_3,Y_3/Z_3)$を満たすように、かつ除算が入らないように$X_3$, $Y_3$, $Z_3$を決めると、
\begin{align*}
 & u:=Y_2Z_1-Y_1Z_2, \quad v:=X_2Z_1-X_1Z_2,\\
 & w:= u^2 Z_1 Z_2 - v^3 - 2v^2 X_1 Z_2,\\
 & X_3 := vw,\\
 & Y_3 := u(v^2 X_1 Z_2-w)-v^3 Y_1 Z_2,\\
 & Z_3 := v^3 Z_1 Z_2
\end{align*}
で求められます。
足し算や引き算、小さな値の定数倍は無視して同じ乗算をしないように、乗算の回数を数えてみると14回必要なことがわかります。

2倍公式も同様にします。
$(x,y)=(X/Z,Y/Z)$として
\[
\lambda = \frac{3x^2+a}{2y}=\frac{3(X/Z)^2+a}{2(Y/Z)}=\frac{3X^2+aZ^2}{2YZ}.
\]
$u:=3X^2+aZ^2$, $v:=YZ$とします。$\lambda=u/(2v)$.
\[
x_3:=\lambda^2-2x_1=\frac{u^2}{4Y^2Z^2}-\frac{2X}{Z}=\frac{u^2-8XY^2Z}{4Y^2Z^2}=\frac{u^2-8XYv}{4v^2}.
\]
$w:=u^2-8XYv$とおくと$x_3=w/(4v^2)$。
$y_3=-(u/2v)(w/(4v^2)-X/Z)-Y/Z$より
\begin{align*}
8v^3y_3 &= -u(w - 4v^2X/Z)-8v^3Y/Z = u(4XY^2Z-w) - 8Y^4Z^2\\
&=u(4XYv-w)-8Y^2v^2.
\end{align*}
よって
\begin{align*}
 & u:=3X^2+aZ^2, \quad v:=YZ, \quad w:= u^2-8XYv,\\
 & X_3:=2vw,\\
 & Y_3:=u(4XYv-w)-8(Yv)^2,\\
 & Z_3:=8v^3
\end{align*}
となります。
有限体の乗算を$M$、逆元操作を$I$として表にまとめます。
\tablecap{楕円曲線上の演算のコスト比較}{
\begin{tabular}{|c|c|c|c|}
\hline
演算の種類   & 加算($P+Q$) & 2倍算($2P$) \\\hline
\hline
アフィン座標  & $3M+I$ & $4M+I$ \\\hline
射影座標      & $14M$  & $12M$ \\\hline
\end{tabular}
}
アフィン座標ではなく射影座標を使ってコストが下がるのは$3M+I \ge 14M$、つまり$I \ge 11M$のときです。
通常逆元操作は乗算操作より数十倍重たいです。
したがって大抵の場合は射影座標を使うとよいことがわかりました。

射影座標を少し変形した$x:=X/Z^2$, $y:=Y/Z^3$という座標系を使うこともあります。
これはJacobi（ヤコビ）座標と呼ばれ、足し算は$16M$、2倍算は$10M$で計算できることが知られています。\index{Jacobiざひょう@Jacobi座標}
2倍算のコストが射影座標より小さいので2倍算を多くする場面で利用されることがあります。

\section{Edwards曲線}
より効率のよい加法公式を持つ楕円曲線の表現がいろいろ研究されています。\cite{EFD}では様々な種類の楕円曲線の公式が紹介されています。
その中からここでは2007年にEdwardsにより提案されたEdwards曲線を紹介します~\cite{Bernstein}。
Edwards曲線は効率のよい楕円曲線の加法が可能なため注目されています。

$k$を標数が2でない体とし、$c, d \in k$で$c \ne 0$, $d \ne 0$, $dc^4 \ne 1$となるものをとります。
\[
x^2+y^2=c^2(1+dx^2 y^2)
\]
で定義される曲線をEdwards曲線といいます。
Edwards曲線は楕円曲線のある特別なグループです。

たとえば$y^2=x^3+4x$というWeierstrassの方程式で定義された楕円曲線を考えます。
\begin{equation}
\label{edwards_trans}
x = \frac{2(1+t)}{1-t}, \quad y = \frac{2x}{s} = \frac{4(1+t)}{(1-t)s}
\end{equation}
という変換を考えます。
この変換は逆写像を作れます。
一つ目の式を$t$について解き、二つ目の式に代入すると
\[
 t = \frac{x-2}{x+2}, \quad s = \frac{2x}{y}
\]
とできるからです。
さて$y^2=x^3+4x$に式（\ref{edwards_trans}）を代入して整理すると
\[
s^2+t^2=1-s^2 t^2
\]
となりました。
これは$c=1$, $d=-1$のEdwards曲線です。
$(x,y) \leftrightarrow (s,t)$は互いに逆写像があるので
$y^2=x^3+4x$はEdwards曲線の形にできることがわかりました。

\section{Edwards曲線の加法公式}
Edwards曲線$x^2+y^2=c^2(1+dx^2y^2)$の2点$P=(x_1,y_1)$, $Q=(x_2,y_2)$が与えられたとき、点$R:=P+Q=(x_3,y_3)$は
\[
(x_3,y_3):=\left(\frac{x_1y_2+y_1x_2}{c(1+dx_1x_2 y_1y_2)},\frac{y_1y_2-x_1x_2}{c(1-dx_1x_2y_1y_2)}\right)
\]
で与えられます。
単位元は$O:=(0,c)$で点$P:=(x_1,y_1)$の逆元は$-P:=(-x_1,y_1)$です。
Weierstrassの方程式上で提案された様々な公式と一番異なるのは加法と2倍算の場合分けが不要なことです。
これにはいくつかのメリットがあります。

まず当たり前ですが$P+Q$で$P=Q$かどうかを気にせずにプログラムのコードを記述できます。
従来の楕円曲線では加法と2倍算の公式が異なるため、通常その実行回路や演算速度が異なります。
するとたとえば楕円曲線暗号が組み込まれたICカードに電極を挿して消費電力やタイミングを測定することで加法と2倍算の違いから秘密鍵を推測できることがありました。
これはサイドチャネル攻撃（side-channel attack）と呼ばれるものの一つです。
Edwards曲線はそれに対して耐性があります。

次に3倍点の公式を作ることができます。
そうするとより効率のよいスカラー倍算を構築できることが知られています。
加法と2倍算の公式が異なると3倍点の公式は場合分けが複雑になり、そのメリットがでません。

またそもそもの目的の一つですが射影座標で計算すると加法は$12M$（$c=1$なら$11M$）、2倍算は$7M$でできることが知られています。

Edwards曲線を少しひねったtwisted Edwards曲線というものがあり、BernsteinたちはEdwards曲線版デジタル署名（EdDSA）を提案しています~\cite{eddsa}。
\section{この章のまとめ}
浮輪の形で定義したトーラスは二重周期関数である$\wp$関数を利用すると$y^2=x^3+ax+b$で定義される楕円曲線と対応がつくことを示しました。
楕円曲線上の点の加法は楕円曲線と直線の交点で表現できます。
これにより暗号で利用できる計算手順を書き下せます。

楕円曲線に登場する無限遠点を統一的に扱うために射影空間を導入しました。
そして楕円曲線上の点の加法は、射影座標を用いるとより高速に計算できました。
楕円曲線の演算性能は非常に重要なので様々な手法が提案されています。