暗号理論の問題

方針 $2P,3P,\dots$ を順に計算して $kP=O$ となる最小の $k$（位数）を見つけ、$2027$ を位数で割った余りにスカラーを下げる。計算はすべて $\mathrm{mod}11$ で行う。

1. $2P$ を求める（2 倍算）
$P=(0,5)$ で $a=1$ なので
$$\lambda =\frac{3\cdot 0^2+1}{2\cdot 5}=\frac{1}{10}.$$
$10\equiv -1(\mathrm{mod}11)$ より $10^{-1}\equiv -1\equiv 10$（実際 $10\cdot 10=100=9\cdot 11+1$）。よって $\lambda =10$。
$$x_3={\lambda }^2-0-0=100\equiv 1,y_3=\lambda (0-x_3)-5=10\cdot (-1)-5=-15\equiv 7.$$
よって $2P=(1,7)$。（確認：$7^2=49\equiv 5$、$1^3+1+3=5$。）

2. $3P=P+2P$ を求める（加算）
$P=(0,5)$, $2P=(1,7)$ より
$$\lambda =\frac{7-5}{1-0}=2,$$
$$x_3=2^2-0-1=3,y_3=2\cdot (0-3)-5=-11\equiv 0.$$
よって $3P=(3,0)$。（確認：$3^3+3+3=33\equiv 0$。）

3. 位数を決める
$3P=(3,0)$ は $y$ 座標が $0$ なので $-3P=(3,-0)=3P$、すなわち $3P+3P=O$ となり $6P=O$。
一方 $P\ne O$、$2P=(1,7)\ne O$、$3P=(3,0)\ne O$ であり、位数は $6$ の約数 $1,2,3,6$ のどれかなので、位数は $6$。

4. スカラーを位数で割った余りに下げる
$2027=6\cdot 337+5$ より
$$2027P=337\cdot (6P)+5P=5P.$$
さらに $5P=6P-P=-P$ であり、$-P=(0,-5)=(0,6)$。

したがって $2027P=(0,6)$。

$f(x)=x^3+x+3$ とおく。

位数の計算。
- $P=(0,5)$ は $5^2=25\equiv 3=f(0)$ より曲線上の点である。
- $2P$ を求める。$\lambda =\frac{3x^2+1}{2y}=\frac{1}{10}\equiv 10(\mathrm{mod}11)$ である。$x_3={\lambda }^2-2x=1$、$y_3=\lambda (0-1)-5=-15\equiv 7$ より $2P=(1,7)$ となる。
- 確認: $7^2=49\equiv 5$、$f(1)=5$ で一致する。
- $3P=P+2P$ を求める。$\lambda =\frac{7-5}{1-0}=2$、$x_3=4-0-1=3$、$y_3=2(0-3)-5=-11\equiv 0$ より $3P=(3,0)$ となる。
- $y=0$ の点なので $2\cdot 3P=O$、すなわち $6P=O$ である。
- $3P\ne O$、$2P\ne O$ であるから、$P$ の位数は $6$ である。
- 参考: $E({\mathbb{F}}_{11})$ の点数は、$x=0,1,4,5,6,7,9,10$ で各 2 点、$x=3$ で 1 点、無限遠点 $O$ で 1 点となり、計 18 点である。位数 $6$ は $18$ の約数で、矛盾しない。

スカラー倍。
$2027=6\cdot 337+5$ より $2027P=5P=-P=(0,-5)=(0,6)$ である。

検算: $6^2=36\equiv 3=f(0)$ で曲線上にある。