暗号理論の問題

加法公式. $P_1=(x_1,y_1)$, $P_2=(x_2,y_2)$ に対し、$P_1\ne \pm P_2$ のとき $\lambda =\frac{y_2-y_1}{x_2-x_1}$、$P_1=P_2$（$y_1\ne 0$）のとき $\lambda =\frac{3x_1^2+2}{2y_1}$ として
$$x_3={\lambda }^2-x_1-x_2,y_3=\lambda (x_1-x_3)-y_1$$
が $P_1+P_2$ の座標である。また $-(x,y)=(x,-y)$ である。計算はすべて $\mathrm{mod}23$ で行う。

$2P$. $\lambda =\frac{3\cdot 0+2}{2\cdot 3}=2\cdot 6^{-1}$。$6\cdot 4=24\equiv 1$ より $6^{-1}\equiv 4$、$\lambda \equiv 8$。
$x=64-0\equiv 18$, $y=8(0-18)-3=-147\equiv 14$。よって $2P=(18,14)$。

$4P=2(2P)$. $18^2=324\equiv 2$ より $3\cdot 2+2=8$、$2\cdot 14=28\equiv 5$、$5^{-1}\equiv 14$（$5\cdot 14=70\equiv 1$）。$\lambda \equiv 8\cdot 14=112\equiv 20$。
$x=400-36=364\equiv 19$, $y=20(18-19)-14=-34\equiv 12$。よって $4P=(19,12)$。

$3P=2P+P$. $\lambda =\frac{3-14}{0-18}=\frac{11}{18}$。$18\cdot 9=162\equiv 1$ より $18^{-1}\equiv 9$、$\lambda \equiv 99\equiv 7$。
$x=49-18-0=31\equiv 8$, $y=7(18-8)-14=56\equiv 10$。よって $3P=(8,10)$。

$7P=4P+3P$. $\lambda =\frac{10-12}{8-19}=\frac{-2}{-11}=\frac{2}{11}$。$11\cdot 21=231\equiv 1$ より $11^{-1}\equiv 21$、$\lambda \equiv 42\equiv 19$。
$x=361-19-8=334\equiv 12$, $y=19(19-12)-12=121\equiv 6$。よって $7P=(12,6)$。

$14P=2(7P)$. $12^2=144\equiv 6$ より $3\cdot 6+2=20$、$2\cdot 6=12$、$12^{-1}\equiv 2$。$\lambda \equiv 40\equiv 17$。
$x=289-24=265\equiv 12$, $y=17(12-12)-6=-6\equiv 17$。よって $14P=(12,17)=-(12,6)=-7P$。

したがって $14P+7P=21P=O$ となり、$P$ の位数は $21=3\cdot 7$ の約数である。

位数が $21$ であること. 位数の候補は $1,3,7,21$。
- $P\ne O$ なので $1$ ではない。
- $3P=(8,10)\ne O$ なので $3$ ではない。
- $7P=(12,6)\ne O$ なので $7$ ではない。

よって $P$ の位数は $21$ である。

（検算: 各点が曲線上にあることを確かめる。例えば $7P=(12,6)$ では $12^3+2\cdot 12+9=1761\equiv 13$、$6^2=36\equiv 13$ で一致する。また、ハッセの定理より $|\#E({\mathbb{F}}_{23})-24|\le 2\sqrt{23}<10$ で、$\#E$ は $21$ の倍数なので $\#E=21$ となり、矛盾はない。）

まず $\#E({\mathbb{F}}_{23})$ を数える。$f(x)=x^3+2x+9\mathrm{mod}23$ が平方剰余（${\mathbb{F}}_{23}$ の 0 でない平方は $\{1,2,3,4,6,8,9,12,13,16,18\}$）となる $x$ を調べる。$f(0)=9,f(1)=12,f(2)=21,f(3)=19,f(4)=12,f(5)=6,f(6)=7,f(7)=21,f(8)=8,f(9)=20,f(10)=17,f(11)=5,f(12)=13,f(13)=1,f(14)=21,f(15)=10,f(16)=20,f(17)=11,f(18)=12,f(19)=6,f(20)=22,f(21)=20,f(22)=6$。平方剰余になるのは $x=0,1,4,5,8,12,13,18,19,22$ の 10 個で、各々 $y$ が 2 つあるので 20 点。無限遠点を加えて $\#E=21$。よってラグランジュの定理より $P$ の位数は $21$ の約数 $1,3,7,21$ のいずれか。\n\n点の加算を計算する（すべて mod 23）。\n- $2P$: $\lambda =(3\cdot 0+2)/(2\cdot 3)=1/3=8$。$x=64-0=18$, $y=8(0-18)-3=-147\equiv 14$。$2P=(18,14)$。（確認: $14^2=196\equiv 12=f(18)$）\n- $3P=2P+P$: $\lambda =(14-3)/(18-0)=11\cdot 9=99\equiv 7$。$x=49-18-0=31\equiv 8$, $y=7(0-8)-3=-59\equiv 10$。$3P=(8,10)$。（確認: $100\equiv 8=f(8)$）。$3P\ne O$ なので位数は 3 ではない（1 でもない）。\n- $6P=2(3P)$: $\lambda =(3\cdot 64+2)/(2\cdot 10)=194/20\equiv 10/20=1/2=12$。$x=144-16=128\equiv 13$, $y=12(8-13)-10=-70\equiv 22$。$6P=(13,22)$。（確認: $22^2=484\equiv 1=f(13)$）\n- $7P=6P+P$: $\lambda =(22-3)/(13-0)=19\cdot 16=304\equiv 5$。$x=25-13-0=12\ne$ 無限遠、よって $7P=(12,\cdot )\ne O$。位数は 7 ではない。\n\n以上より位数は $1,3,7$ のどれでもなく、$21$。（$E({\mathbb{F}}_{23})$ は位数 21 の巡回群で $P$ はその生成元。）