暗号理論の問題

$E:y^2=x^3+ax+b$（$a=4$, $b=1$）上の点の加法の公式を使う。計算はすべて法 $19$ で行う。

• 異なる点 $(x_1,y_1)$, $(x_2,y_2)$（$x_1\ne x_2$）の和：$\lambda =\frac{y_2-y_1}{x_2-x_1}$
• 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$ である（2 倍のときは $x_2=x_1$）。

$P$ が $E$ 上にあることの確認。 $0^3+4\cdot 0+1=1=1^2$ なので $P=(0,1)\in E$。

$2P$ を求める。
$$\lambda =\frac{3\cdot 0^2+4}{2\cdot 1}=\frac{4}{2}=2.$$
$$x_3=2^2-0-0=4,y_3=2(0-4)-1=-9\equiv 10(\mathrm{mod}19).$$
よって $2P=(4,10)$。（確認：$4^3+4\cdot 4+1=81\equiv 5$, $10^2=100\equiv 5(\mathrm{mod}19)$ で一致する。）

$3P=2P+P$ を求める。 $(x_1,y_1)=(0,1)$, $(x_2,y_2)=(4,10)$ とすると $x_1\ne x_2$ なので
$$\lambda =\frac{10-1}{4-0}=9\cdot 4^{-1}.$$
$4\cdot 5=20\equiv 1(\mathrm{mod}19)$ より $4^{-1}\equiv 5$。よって $\lambda \equiv 9\cdot 5=45\equiv 7(\mathrm{mod}19)$。
$$x_3=7^2-0-4=45\equiv 7,y_3=7(0-7)-1=-50\equiv 7(\mathrm{mod}19).$$
よって $3P=(7,7)$。

確認。 $7^3+4\cdot 7+1=372=19\cdot 19+11\equiv 11$、$7^2=49=2\cdot 19+11\equiv 11(\mathrm{mod}19)$ で、$(7,7)$ は確かに $E$ 上にある。

答え：$(7,7)$

まず $P=(0,1)$ が $E$ 上にあることを確認する: $0+0+1=1=1^2$。

$2P$ の計算: 接線の傾き $\lambda =\frac{3x_1^2+4}{2y_1}=\frac{4}{2}=2$。$x_3={\lambda }^2-2x_1=4-0=4$、$y_3=\lambda (x_1-x_3)-y_1=2(0-4)-1=-9\equiv 10(\mathrm{mod}19)$。よって $2P=(4,10)$。
確認: $4^3+4\cdot 4+1=81\equiv 5$、$10^2=100\equiv 5(\mathrm{mod}19)$ で一致。

$3P=P+2P$ の計算: $P=(0,1),2P=(4,10)$。傾き $\lambda =\frac{10-1}{4-0}=\frac{9}{4}$。$4^{-1}\equiv 5(\mathrm{mod}19)$（$4\cdot 5=20\equiv 1$）なので $\lambda \equiv 9\cdot 5=45\equiv 7$。
$x_3={\lambda }^2-x_1-x_2=49-0-4=45\equiv 7$、$y_3=\lambda (x_1-x_3)-y_1=7(0-7)-1=-50\equiv 7(\mathrm{mod}19)$（$-50+57=7$）。よって $3P=(7,7)$。

検算: $7^3+4\cdot 7+1=343+28+1=372=19\cdot 19+11\equiv 11$、$7^2=49=2\cdot 19+11\equiv 11$ で曲線上の点である。