暗号理論の問題

手順 0：点が曲線上にあることの確認

$P=(2,4)$：$4^2=16\equiv 5$、$2^3+3\cdot 2+2=16\equiv 5(\mathrm{mod}11)$ なので $E$ 上にある。

$Q=(7,5)$：$5^2=25\equiv 3$、$7^3+3\cdot 7+2=366=33\cdot 11+3\equiv 3(\mathrm{mod}11)$ なので $E$ 上にある。

$x$ 座標が異なる（$2\ne 7$）ので、$P+Q\ne O$ であり、異なる 2 点の加算の公式を使う。

手順 1：傾き $\lambda$ を求める

$$\lambda =\frac{y_2-y_1}{x_2-x_1}=\frac{5-4}{7-2}=\frac{1}{5}(\mathrm{mod}11).$$

$5^{-1}\mathrm{mod}11$ を互除法で求める。$11=2\cdot 5+1$ より
$$1=11-2\cdot 5$$
なので $5\cdot (-2)\equiv 1(\mathrm{mod}11)$、すなわち $5^{-1}\equiv -2\equiv 9(\mathrm{mod}11)$。（確認：$5\cdot 9=45=4\cdot 11+1$。）

よって $\lambda \equiv 1\cdot 9=9(\mathrm{mod}11)$。

手順 2：$x_3$ を求める

$$x_3={\lambda }^2-x_1-x_2=81-2-7=72=6\cdot 11+6\equiv 6(\mathrm{mod}11).$$

手順 3：$y_3$ を求める

$$y_3=\lambda (x_1-x_3)-y_1=9\cdot (2-6)-4=-36-4=-40\equiv -40+44=4(\mathrm{mod}11).$$

検算：$(6,4)$ について $4^2=16\equiv 5$、$6^3+3\cdot 6+2=236=21\cdot 11+5\equiv 5(\mathrm{mod}11)$ なので、確かに $E$ 上の点である。

したがって $P+Q=(6,4)$、答えは $(x_3,y_3)=(6,4)$。

まず $P,Q$ が $E$ 上にあることを確かめる。$P=(2,4)$ では $y^2=16\equiv 5$、$x^3+3x+2=8+6+2=16\equiv 5$ で一致する。$Q=(7,5)$ では $y^2=25\equiv 3$、$x^3+3x+2=343+21+2\equiv 2+10+2=14\equiv 3$ で一致する。

$x_P\ne x_Q$ なので傾きは $\lambda =\frac{5-4}{7-2}=5^{-1}(\mathrm{mod}11)$。$5\cdot 9=45\equiv 1$ より $\lambda =9$ である。

$x_3={\lambda }^2-x_1-x_2=81-2-7=72\equiv 72-66=6$。

$y_3=\lambda (x_1-x_3)-y_1=9(2-6)-4=-40\equiv -40+44=4$。

検算として $(6,4)$ が $E$ 上にあるか確かめる。$y^2=16\equiv 5$、$x^3+3x+2=216+18+2=236=11\cdot 21+5\equiv 5$ で一致する。

よって $P+Q=(6,4)$。