大学数学基礎解説

楕円曲線の加法の結合法則を初等的に証明する話

群論,楕円曲線

楕円曲線の加法の結合法則を計算機を使わずに初等的に証明する方法を紹介します。この方法は本当になんでもないありきたりなヒラメキですが、びっくりするほど計算が簡単になります。内容は高校生でも大丈夫だと思います。

楕円曲線

$K$を体とします。体を知らない人は$\mathbb{R}$だと思って問題ありません。

$K$の元$a_1,a_2,a_3,a_4,a_6\in K$をパラメーターとする楕円曲線とは、次の方程式を満たす$(x,y)\in K^2$が作る図形$E$のことです。

$$E: y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$$

これに、もう1点無限遠点$\mathcal{O}$を追加して考えます。

楕円曲線の点の加法

以下、パラメーター$a_1,a_2,a_3,a_4,a_6$は固定して、ひとつの楕円曲線を考えます。この楕円曲線の2点$P,Q$に対してその和$P+Q$を定めたいのですが、その前に$-P$を決めましょう。

$P$は無限遠点であるか、上記の方程式を満たす座標$(x,y)$ですから、無限遠点の場合は$-P:=\mathcal{O}$と定めます。そうでない場合は

$$-P := (x, -y-a_1x-a_3)$$

で定めます。

次に$P,Q$の和を定義しましょう。少なくとも片方が無限遠点の場合は、$\mathcal{O}+\mathcal{O}:=\mathcal{O}, P+\mathcal{O}:=P, \mathcal{O}+Q:=Q$で定めます。そうではなく、$P=-Q$であった場合は$P+Q:=\mathcal{O}$で定めます。それでもない場合は、$P=(x_P,y_P),Q=(x_Q,y_Q)$として$P+Q$の座標$(x,y)$を以下で定めます。

$$x:=\lambda^2+a_1\lambda-a_2-x_P-x_Q,$$
$$y:=-(\lambda+a_1)x-\nu-a_3$$

ここで、$\lambda$と$\nu$は以下の値です。

$$\lambda:=\begin{cases} \dfrac{y_Q-y_P}{x_Q-x_P} & (x_P\neq x_Q),\\ \dfrac{3x_P^2+2a_2x_P+a_4-a_1y_P}{2y_P+a_1x_P+a_3} & (x_P = x_Q) \end{cases} $$
$$\nu:=\begin{cases} \dfrac{y_Px_Q-y_Qx_P}{x_Q-x_P} & (x_P\neq x_Q),\\ \dfrac{-x_P^3+a_4x_P+2a_6-a_3y_P}{2y_P+a_1x_P+a_3} & (x_P = x_Q) \end{cases}$$

これで楕円曲線上の2点に対してその和が定義されました。式だけを見ると複雑ですが、$P,Q,-(P+Q)$は一直線上に並んだ楕円曲線上の点になり、$\lambda$と$\nu$は傾きと切片になります。

結合法則

この加法が結合法則を満たすことを示しましょう。結合法則というのは、任意の点$P,Q,R$にたいして、

(P+Q)+R=P+(Q+R)

が成り立つことでした。交換法則

P+Q=Q+P

は定義から簡単に証明できます。一方で、結合法則の証明は大変です。和の定義の場合分けがややこしいので、今回は途中に出てくる和はすべて$x_P\neq x_Q$の場合を使って計算する分岐を通ってきたと仮定しましょう。$P,Q,R,P+Q,Q+R,(P+Q)+R,P+(Q+R)$の座標をそれぞれ、$(x_P,y_P),(x_Q,y_Q),(x_R,y_R),(x_{PQ},y_{PQ}),(x_{QR},y_{QR}),(x_{(PQ)R},y_{(PQ)R}),(x_{P(QR)},y_{P(QR)})$と書くことにします。

示すべきことは、

$x_{(PQ)R}=x_{P(QR)}$かつ$y_{(PQ)R}=y_{P(QR)}$

です。このとき、$P,Q,R$は楕円曲線上の点ですから

$$y_P^2+a_1x_Py_P+a_3y_P=x_P^3+a_2x_P^2+a_4x_P+a_6$$
$$y_Q^2+a_1x_Qy_Q+a_3y_Q=x_Q^3+a_2x_Q^2+a_4x_Q+a_6$$
$$y_R^2+a_1x_Ry_R+a_3y_R=x_R^3+a_2x_R^2+a_4x_R+a_6$$

を使うことができます。もっと簡単に書くと$x_{(PQ)R}-x_{P(QR)}$を定義に従って展開して、

\begin{align} x_{(PQ)R}-x_{P(QR)}&=(x_P^3+a_2x_P^2+a_4x_P+a_6-y_P^2-a_1x_Py_P-a_3y_P)F\\ &+(x_Q^3+a_2x_Q^2+a_4x_Q+a_6-y_Q^2-a_1x_Qy_Q-a_3y_Q)G\\ &+(x_R^3+a_2x_R^2+a_4x_R+a_6-y_R^2-a_1x_Ry_R-a_3y_R)H \end{align}

となる有理式$F,G,H$を見つければよいことになります($y$座標についても同様)。この計算は計算機にやらせると秒で終わります。しかし、でてきた$F,G,H$は人間が理解できる範囲を超越した複雑な式になってしまい、単純に展開したら等しいでしょと言われても困ってしまいます。

この記事の目標はこの計算を人間でも力づくでできるように簡略化することです。

変数変換

まずは変数の数が多すぎるので、一般性を失わず$(x_Q,y_Q)=(0,0)$としてよいことを見ましょう。変数変換

\begin{align} x &= x' + x_Q,\\ y &= y' + y_Q\\ \end{align}

を行うと、楕円曲線の方程式は

$$E': y'^2+a'_1x'y'+a'_3y=x'^3+a'_2x'^2+a'_4x+a'_6$$

に変化します。ここで、

\begin{align} a'_1 &:= a_1, \\ a'_2 &:= a_2+3x_Q, \\ a'_3 &:= a_3+x_Qa_1+2y_Q, \\ a'_4 &:= a_4+2x_Qa_2-y_Qa_1+3x_Q^2, \\ a'_6 &:= a_6+x_Qa_4+x_Q^2a_2+x_Q^3-y_Qa_3-y_Q^2-x_Qy_Qa_1, \\ \end{align}

となります。この変換で点$P,Q,R$は点$P'=(x_P-x_Q,y_P-y_Q),Q'=(0,0),R'=(x_R-x_Q,y_R-y_Q)$に移ります。この変換は平行移動しただけで、3点が一直線上にあるという性質を保存しますから、この新しい楕円曲線上で、$(P'+Q')+R'=P'+(Q'+R')$を示せばよいことになります。$P'=(x'_P,y'_Q),R'=(x'_R,y'_R)$と変数を置きなおせば、結局のところ、一般性を失わずに$Q=(0,0)$としてよかったということがわかります。

変数変換が$u\neq 0$と$r,s,t\in K$に対して、

\begin{align} x &= u^2x' + r,\\ y &= u^3y' + u^2sx' + t\\ \end{align}

の形をしていれば、上の議論はいつでも使うことができ、$Q=(0,0)$にした後に、これを保ったまま一般性を失わず$y_P=0$にでき、さらに$x_R=y_R$とできます。よって、今回仮定した場合では、一般性を失わず$P=(s,0),Q=(0,0),R=(t,t)$としてよいことが分かります。これらは楕円曲線上の点なので、

$$0=s^3+a_2s^2+a_4s+a_6,$$
$$0=a_6,$$
$$t^2+a_1t^2+a_3t=t^3+a_2t^2+a_4t+a_6$$

を満たします。これを使って計算するとまったく簡単に

$$x_{(PQ)R}=x_{P(QR)}=(s-t)(s-t+a_1+1),$$
$$y_{(PQ)R}=x_{P(QR)}=((s-t)^2-t)(s-t+a_1+1)-a_3$$

を求めることができます。