暗号理論の問題

以下、計算はすべて法 $13$ で行う。${\mathbb{F}}_{13}$ での逆元は $2^{-1}=7,3^{-1}=9,4^{-1}=10,5^{-1}=8,6^{-1}=11,9^{-1}=3,10^{-1}=4,11^{-1}=6$ である。

まず $P=(1,3)$ が $E$ 上にあることを確かめる：$1+3+5=9=3^2$。また $4\cdot 3^3+27\cdot 5^2=108+675=783\equiv 3\not\equiv 0$ なので $E$ は非特異である。

加法公式　$P_1=(x_1,y_1)$, $P_2=(x_2,y_2)$ に対し、傾き $\lambda$ を
$$\lambda =\frac{y_2-y_1}{x_2-x_1}(P_1\ne P_2),\lambda =\frac{3x_1^2+3}{2y_1}(P_1=P_2)$$
として $x_3={\lambda }^2-x_1-x_2$, $y_3=\lambda (x_1-x_3)-y_1$ が $P_1+P_2$ の座標である（$x_1=x_2,y_1=-y_2$ のときは $P_1+P_2=O$）。

$2P$　$\lambda =\frac{3\cdot 1+3}{2\cdot 3}=\frac{6}{6}=1$。$x_3=1-2=-1\equiv 12$, $y_3=1\cdot (1-12)-3=-14\equiv 12$。よって $2P=(12,12)$。

$4P=2(2P)$　$\lambda =\frac{3\cdot 12^2+3}{2\cdot 12}$。$12^2=144\equiv 1$ より分子は $6$、分母は $24\equiv 11$。$\lambda =6\cdot 11^{-1}=6\cdot 6=36\equiv 10$。$x_3=100-24=76\equiv 11$, $y_3=10\cdot (12-11)-12=-2\equiv 11$。よって $4P=(11,11)$。

$5P=4P+P$　$\lambda =\frac{3-11}{1-11}=\frac{-8}{-10}=\frac{8}{10}=8\cdot 4=32\equiv 6$。$x_3=36-11-1=24\equiv 11$, $y_3=6\cdot (11-11)-11=-11\equiv 2$。よって $5P=(11,2)$。

$5P$ と $4P=(11,11)$ は $x$ 座標が等しく、$y$ 座標は $2+11=13\equiv 0$ より互いに符号が逆である。したがって $5P=-4P$、すなわち $9P=O$ である。$P$ の位数は $9$ の約数であり、$P\ne O$, $3P\ne O$（$3P=P+2P$ を計算すると $\lambda =\frac{12-3}{12-1}=9\cdot 6\equiv 2$, $x_3=4-1-12\equiv 4$, $y_3=2(1-4)-3\equiv 4$ で $3P=(4,4)\ne O$）なので、$P$ の位数はちょうど $9$ である。

（検算）$8P=2(4P)$ を計算すると $\lambda =\frac{3\cdot 121+3}{22}\equiv \frac{2}{9}=2\cdot 3=6$, $x_3=36-22=14\equiv 1$, $y_3=6(11-1)-11=49\equiv 10$ で $8P=(1,10)=-P$ となり、$9P=O$ と矛盾しない。

$2030P$　$2030=9\cdot 225+5$ なので
$$2030P=225\cdot (9P)+5P=5P=(11,2).$$

まず群の位数を求める。$f(x)=x^3+3x+5\mathrm{mod}13$ を $x=0,\dots ,12$ で計算すると、平方剰余（$\{1,3,4,9,10,12\}$）になるのは $f(1)=9$, $f(4)=3$, $f(11)=4$, $f(12)=1$ のみで、それぞれ $y$ が 2 つずつ。他の $x$ では $f(x)\in \{5,6,2,2,5,5,8,7,8\}$ で平方非剰余。したがってアフィン点は 8 個、無限遠点を加えて $|E({\mathbb{F}}_{13})|=9$。ラグランジュの定理より $9P=O$。

$2030=9\cdot 225+5$ なので $2030P=5P$。

$2P$: $\lambda =\frac{3\cdot 1^2+3}{2\cdot 3}=1$, $x=1-2=-1\equiv 12$, $y=1\cdot (1-12)-3=-14\equiv 12$。よって $2P=(12,12)$。

$4P=2(2P)$: $\lambda =\frac{3\cdot 12^2+3}{2\cdot 12}=\frac{6}{11}\equiv 6\cdot 6=36\equiv 10$（$11^{-1}\equiv 6$）。$x=100-24=76\equiv 11$, $y=10(12-11)-12=-2\equiv 11$。よって $4P=(11,11)$。

$5P=4P+P$: $\lambda =\frac{3-11}{1-11}=\frac{-8}{-10}=\frac{4}{5}\equiv 4\cdot 8=32\equiv 6$（$5^{-1}\equiv 8$）。$x=36-11-1=24\equiv 11$, $y=6(11-11)-11=-11\equiv 2$。よって $5P=(11,2)$。

検算: $(11,2)$ は $2^2=4=f(11)$ を満たす。また $5P=-4P$（$4P=(11,11)$ の逆元は $(11,2)$）であり、$9P=O$ と整合する。