暗号理論の問題

${\mathbb{F}}_{17}$ での計算なので、割り算は逆元を掛けて行う。$y^2=x^3+ax+b$（$a=3$）上の加法公式は次のとおりである。
- $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+a}{2y_1}$ とし、
$$x_3={\lambda }^2-x_1-x_2,y_3=\lambda (x_1-x_3)-y_1.$$
- $(x,y)+(x,-y)=O$。特に $y=0$ の点は $2$ 倍すると $O$ になる。

まず $P,Q$ が $E$ 上にあることを確かめる: $0^3+0+4=4=2^2$、$1+3+4=8$ で $5^2=25\equiv 8(\mathrm{mod}17)$。

$2P$: $\lambda =\frac{3\cdot 0^2+3}{2\cdot 2}=3\cdot 4^{-1}$。$4\cdot 13=52\equiv 1$ より $4^{-1}=13$ なので $\lambda =39\equiv 5$。
$$x=25-0-0=25\equiv 8,y=5(0-8)-2=-42\equiv 9.$$
よって $2P=(8,9)$。

$3P=2P+P$: $\lambda =\frac{2-9}{0-8}=\frac{-7}{-8}=7\cdot 8^{-1}$。$8\cdot 15=120\equiv 1$ より $8^{-1}=15$ なので $\lambda =105\equiv 3$。
$$x=9-8-0=1,y=3(0-1)-2=-5\equiv 12.$$
よって $3P=(1,12)$。これは $Q=(1,5)$ と $x$ 座標が同じで、$12\equiv -5$ だから $3P=-Q$ である。

$4P=3P+P$: $\lambda =\frac{2-12}{0-1}=10$。
$$x=100-1-0=99\equiv 14,y=10(0-14)-2=-142\equiv 11.$$
よって $4P=(14,11)$。（$2\cdot (2P)$ で計算しても $\lambda =\frac{3\cdot 64+3}{18}\equiv 8$、$x=64-16\equiv 14$、$y=8(8-14)-9\equiv 11$ で一致する。）

$5P=4P+P$: $\lambda =\frac{2-11}{0-14}=\frac{-9}{-14}=9\cdot 14^{-1}$。$14\cdot 11=154\equiv 1$ より $14^{-1}=11$ なので $\lambda =99\equiv 14$。
$$x=196-14-0=182\equiv 12,y=14(0-12)-2=-170\equiv 0.$$
よって $5P=(12,0)$。$y$ 座標が $0$ なので $10P=2(5P)=O$ であり、$P$ の位数は $10$ の約数である。$P,2P,\dots ,5P$ はどれも $O$ ではないので、$P$ の位数は $10$（位数が $10$ の約数 $1,2,5$ ならそれぞれ $P$, $2P$, $5P$ のどれかが $O$ になるが、どれも $O$ でない）。

したがって $6P=-4P=(14,-11)=(14,6)$、$7P=-3P=(1,-12)=(1,5)$、$8P=-2P=(8,8)$、$9P=-P=(0,15)$ となる。

$1\le k\le 6$ では $kP$ はそれぞれ $(0,2),(8,9),(1,12),(14,11),(12,0),(14,6)$ で、どれも $Q$ と一致しない。$7P=(1,5)=Q$ なので、求める最小の $k$ は
$$k=7.$$
（$kP=Q$ を満たす正の整数 $k$ は $k\equiv 7(\mathrm{mod}10)$ のものすべてである。）

まず $P,Q$ が曲線上にあることを確認する（mod 17）。$P=(0,2)$: $y^2=4$, $x^3+3x+4=4$ ✓。$Q=(1,5)$: $y^2=25\equiv 8$, $1+3+4=8$ ✓。\n\n$P$ の倍数を順に計算する（逆元: $2^{-1}=9$, $4^{-1}=13$, $8^{-1}=15$, $14^{-1}=11$ など）。\n- $2P$: $\lambda =(3\cdot 0^2+3)/(2\cdot 2)=3\cdot 13=39\equiv 5$。$x=25-0=25\equiv 8$, $y=5(0-8)-2=-42\equiv 9$。$2P=(8,9)$。（確認: $81\equiv 13$, $8^3+24+4=540\equiv 13$ ✓）\n- $3P=2P+P$: $\lambda =(9-2)/(8-0)=7\cdot 15=105\equiv 3$。$x=9-8-0=1$, $y=3(0-1)-2=-5\equiv 12$。$3P=(1,12)$。\n- $4P=3P+P$: $\lambda =(12-2)/(1-0)=10$。$x=100-1-0=99\equiv 14$, $y=10(0-14)-2=-142\equiv 11$。$4P=(14,11)$。（確認: $121\equiv 2$, $14^3+42+4=2790\equiv 2$ ✓）\n- $5P=4P+P$: $\lambda =(11-2)/(14-0)=9\cdot 11=99\equiv 14$。$x=196-14-0=182\equiv 12$, $y=14(0-12)-2=-170\equiv 0$。$5P=(12,0)$。\n\n$y=0$ の点は位数 2 なので $10P=O$、$P$ の位数は 10 の約数で、$2P\ne O$, $5P\ne O$ より位数はちょうど 10。したがって $P$ の倍数 $kP$（$k=1,\dots ,10$）は互いに異なる。\n\n続けて $6P=5P+P$: $5P=(12,0)$, $P=(0,2)$、$\lambda =(2-0)/(0-12)=2/5=2\cdot 7=14$。$x=196-12-0=184\equiv 14$, $y=14(12-14)-0=-28\equiv 6$。$6P=(14,6)$（$=-4P$ ✓）。\n$7P=6P+P$: $\lambda =(2-6)/(0-14)=(-4)/(-14)=4/14=4\cdot 11=44\equiv 10$。$x=100-14-0=86\equiv 1$, $y=10(14-1)-6=124\equiv 124-119=5$。$7P=(1,5)=Q$。\n\n（別の確認: $3P=(1,12)=-Q$ だったので $Q=-3P=7P$。）\n\n$P$ の位数が 10 なので $kP=Q$ を満たす最小の正の整数は $k=7$。