楕円曲線入門 (2)

前回の楕円曲線入門では曲線上における演算について解説した.
今回は点のスカラー倍と群構造について解説する.

スカラー倍

前回は足し算と2倍について解説したが, 任意の定数倍はどうすればいいだろうか.
たとえば, Pの100倍である100Pを得るには2PにPを98回足せばよいが¹, 2¹⁰⁰倍するとなると2¹⁰⁰-2回の足し算を行うことになる². これは現実的でないためどうにかしたい.

+ P と * 2 だけで効率的に定数倍を求める(計算量を落とす)ことができればよいだろう.

100Pの場合は

\begin{eqnarray*} 100P & = & 4 * 25P \newline & = & 2^{2} (P + 24P) \newline & = & 2^{2} (P + 8*3P) \newline & = & 2^{2} (P + 2^{3}(P + 2P)) \newline \end{eqnarray*}

2倍, 足し算, 2倍を3回, 足し算, 2倍を2回 の計8回の処理で100倍が得られる.

楕円曲線が持つ群構造

曲線状の点は整数点のみを考える.

p = 11 の例

11を法とすると, 同値類の代表元から得られる集合とその位数は{0, 1, .., 10}で11個である.
曲線にはx座標とy座標があるため, (x, y)の組み合わせは

(0, 0), (0, 1), .., (0, 10)   
(1, 0), (1, 1), .., (1, 10)
.  
.  
(10, 0), (10, 1), .., (10, 10)

以上の121個となる. この中から目的の楕円曲線の式を満たす(x, y)の組み合わせを取り出すと楕円曲線の最大の位数が得られる. (厳密には起点から無限遠点までにいくつの点が存在するかをその楕円曲線の位数とするので "最大の"という表現を使っている. base pointをどこにするかで位数が変わるので, セキュリティのためにもbase pointを適当に選んではいけない)

ある点Pをbase pontとして,

P -> 2P  
2P -> 3P   
3P -> ...  

と繰り返していくといつか無限遠点Oにたどり着き, 最終的にPに戻ってくる. つまり巡回"群"の体を成している.
これは
\( aP = O; \) となる\(a \, (a < p )\)が存在し \( O + P = P \) であることから言える.

To be continued

第3話

1: 64Pまで2倍を繰り返してから足し算に移行するなど, 他にもいくつか方法はある
2: 2倍を100回繰り返せばいいのだが, 100bits相当の定数倍というニュアンスで