暗号理論の問題

準備 $P=(4,1)$ が $E$ 上にあることを確かめる。$4^3+4+3=71\equiv 1(\mathrm{mod}7)$、$1^2=1$ なので、確かに $E$ 上の点である。計算では $2^{-1}\equiv 4(\mathrm{mod}7)$（$2\cdot 4=8\equiv 1$）を使う。

$2027P$ を直接求めるのは大変なので、まず $P$ の位数（$kP=O$ となる最小の正の整数 $k$）を求め、スカラー $2027$ をその位数で割った余りに下げる。

手順1：$2P$ を求める（2倍算）
$$\lambda =\frac{3x_1^2+a}{2y_1}=\frac{3\cdot 16+1}{2\cdot 1}=\frac{49}{2}\equiv 0(\mathrm{mod}7)$$
$$x_3={\lambda }^2-2x_1=0-8\equiv 6,y_3=\lambda (x_1-x_3)-y_1=0-1\equiv 6(\mathrm{mod}7)$$
よって $2P=(6,6)$。（確認：$6^3+6+3=225\equiv 1$、$6^2=36\equiv 1$。）

手順2：$3P=2P+P$ を求める（加算）
$$\lambda =\frac{6-1}{6-4}=\frac{5}{2}\equiv 5\cdot 4=20\equiv 6(\mathrm{mod}7)$$
$$x_3={\lambda }^2-x_1-x_2=36-4-6=26\equiv 5,y_3=6(4-5)-1=-7\equiv 0(\mathrm{mod}7)$$
よって $3P=(5,0)$。（確認：$5^3+5+3=133=7\cdot 19\equiv 0$。）

手順3：位数を決める
$3P=(5,0)$ は $y$ 座標が $0$ なので $-3P=(5,-0)=(5,0)=3P$ である。したがって $6P=3P+3P=3P+(-3P)=O$。
また $P,2P,3P$ はいずれも $O$ ではなく、$4P=6P-2P=-2P=(6,1)\ne O$、$5P=6P-P=-P=(4,6)\ne O$ である。よって $P$ の位数は $6$。

手順4：スカラーを位数で割った余りに下げる
$2027=6\cdot 337+5$ なので $2027\equiv 5(\mathrm{mod}6)$。$6P=O$ より
$$2027P=337\cdot (6P)+5P=5P=-P$$
$-P$ は $P=(4,1)$ の $y$ 座標の符号を変えた点で、$-1\equiv 6(\mathrm{mod}7)$ だから
$$2027P=(4,6)$$

まず $E({\mathbb{F}}_7)$ の点を数える。平方数は $0,1,2,4$ である。
- $x=0$: $3$ は平方数でないので点なし。
- $x=1$: $5$ は平方数でないので点なし。
- $x=2$: $13\equiv 6$ は平方数でないので点なし。
- $x=3$: $33\equiv 5$ は平方数でないので点なし。
- $x=4$: $71\equiv 1$ より $y=1,6$。
- $x=5$: $133\equiv 0$ より $y=0$。
- $x=6$: $225\equiv 1$ より $y=1,6$。

有理点は $O$ を含めて $6$ 個なので、群の位数は $6$ である。

次に $P=(4,1)$ の位数を求める。

$2P$: 傾き $\lambda =(3\cdot 16+1)/(2\cdot 1)=49/2\equiv 0$。$x_3=0-8\equiv 6$、$y_3=0\cdot (4-6)-1\equiv 6$。よって $2P=(6,6)$。

$3P=2P+P$: 傾き $\lambda =(6-1)/(6-4)=5\cdot 2^{-1}=5\cdot 4=20\equiv 6$。$x_3=36-6-4=26\equiv 5$、$y_3=6(4-5)-1=-7\equiv 0$。よって $3P=(5,0)$ で、これは位数 $2$ の点である。

したがって $6P=O$ で、$P$ の位数は $6$（$2P\ne O$、$3P\ne O$ より）である。

$2027=6\cdot 337+5$ より $2027P=5P=-P=(4,-1)=(4,6)$。

検算: $(4,6)$ について $6^2=36\equiv 1$ で、$x=4$ のとき右辺も $1$ なので曲線上にある。