暗号理論の問題

確認 $P=(5,1)$ は $E$ 上の点である。実際、$5^3+3\cdot 5+1=141=7\cdot 20+1\equiv 1$、$1^2=1$ である。

手順 1: $2P$ を求める（2 倍算）
$a=3$ なので
$$\lambda =\frac{3x_1^2+a}{2y_1}=\frac{3\cdot 25+3}{2\cdot 1}=\frac{78}{2}=39\equiv 4(\mathrm{mod}7).$$
$$x_3={\lambda }^2-2x_1=16-10=6,y_3=\lambda (x_1-x_3)-y_1=4(5-6)-1=-5\equiv 2.$$
よって $2P=(6,2)$ である（確認: $6^3+3\cdot 6+1=235\equiv 4$、$2^2=4$）。

手順 2: $3P=2P+P$ を求める（加算）
$(6,2)+(5,1)$ について
$$\lambda =\frac{1-2}{5-6}=\frac{-1}{-1}=1.$$
$$x_3=1^2-6-5=-10\equiv 4,y_3=1\cdot (6-4)-2=0.$$
よって $3P=(4,0)$ である（確認: $64+12+1=77\equiv 0$）。

手順 3: 位数を決める
$3P=(4,0)$ は $y$ 座標が $0$ なので $-(3P)=(4,-0)=3P$ となる。したがって $3P+3P=O$、すなわち $6P=O$ である。
一方、$P,2P,3P$ はどれも $O$ ではない。また、$4P=O$ とすると $P=4P-3P=-3P=3P$ となり $P\ne 3P$ に反し、$5P=O$ とすると $P=6P-5P=O$ となり矛盾する。よって $4P\ne O$、$5P\ne O$ であり、$kP=O$ となる最小の正の整数 $k$ は $6$ である。つまり $P$ の位数は $6$ である。

手順 4: スカラーを位数で割った余りに下げる
$1000=6\cdot 166+4$ なので
$$1000P=166\cdot (6P)+4P=O+4P=4P.$$
さらに $4P=6P-2P=-2P$ である。点 $(x,y)$ の逆元は $(x,-y)$ なので
$$4P=-(6,2)=(6,-2)=(6,5).$$

したがって $1000P=(6,5)$ である。

まず $P=(5,1)$ が $E$ 上にあることを確かめる。$5^3+3\cdot 5+1=141\equiv 1(\mathrm{mod}7)$ で、$y^2=1$ なので一致する。

$2P$ の計算: 傾きは $\lambda =(3x^2+3)/(2y)=78/2=39\equiv 4$。$x_3={\lambda }^2-2x=16-10=6$。$y_3=\lambda (5-6)-1=-5\equiv 2$。よって $2P=(6,2)$。確認: $6^3+18+1=235\equiv 4=2^2$ で一致する。

$3P=2P+P$ の計算: $\lambda =(2-1)/(6-5)=1$。$x_3=1-6-5=-10\equiv 4$。$y_3=\lambda (6-4)-2=0$。よって $3P=(4,0)$。

$y=0$ の点は位数 2 の点なので $6P=O$ である。$2P\ne O$、$3P\ne O$ なので、$P$ の位数は $6$ である。位数が 12 の約数であることとも整合する。$E({\mathbb{F}}_7)$ の点の個数を数えると、$x=0,2,3,5,6$ で各 2 点、$x=4$ で 1 点、無限遠点を加えて 12 個になる。

$1000=6\cdot 166+4$ より $1000P=4P$ である。$6P=O$ なので $4P=-2P=(6,-2)=(6,5)$。

検算: $2P+2P$ を直接計算すると、$\lambda =(3\cdot 36+3)/(2\cdot 2)=111/4$。$111\equiv 6$、$4^{-1}=2$ なので $\lambda =12\equiv 5$。$x_3=25-12=13\equiv 6$。$y_3=5(6-6)-2=-2\equiv 5$。よって $4P=(6,5)$ となり一致する。