暗号理論の問題

方針 $P\ne Q$ で、$x$ 座標が異なる（$6\ne 10$）ので、$Q\ne -P$ であり $P+Q\ne O$ である。したがって、異なる 2 点の加算の公式
$$\lambda =\frac{y_2-y_1}{x_2-x_1},x_3={\lambda }^2-x_1-x_2,y_3=\lambda (x_1-x_3)-y_1$$
を、すべて $\mathrm{mod}11$ で計算する。

確認 $P=(6,2)$: 左辺 $2^2=4$、右辺 $6^3+2\cdot 6+7=235=11\cdot 21+4\equiv 4$。$Q=(10,9)$: 左辺 $81=11\cdot 7+4\equiv 4$、右辺 $1000+20+7=1027=11\cdot 93+4\equiv 4$。どちらも $E$ 上の点である。

手順 1：傾き $\lambda$ を求める
$$\lambda =\frac{9-2}{10-6}=\frac{7}{4}=7\cdot 4^{-1}(\mathrm{mod}11).$$
$4^{-1}\mathrm{mod}11$ を求める。互除法で $11=4\cdot 2+3$, $4=3\cdot 1+1$ より、逆にたどると
$$1=4-3=4-(11-4\cdot 2)=4\cdot 3-11$$
なので $4\cdot 3\equiv 1(\mathrm{mod}11)$、すなわち $4^{-1}\equiv 3$。よって
$$\lambda \equiv 7\cdot 3=21\equiv 10(\mathrm{mod}11).$$

手順 2：$x_3$ を求める
$$x_3={\lambda }^2-x_1-x_2=100-6-10=84=11\cdot 7+7\equiv 7(\mathrm{mod}11).$$

手順 3：$y_3$ を求める
$$y_3=\lambda (x_1-x_3)-y_1=10\cdot (6-7)-2=-12\equiv -12+22=10(\mathrm{mod}11).$$

検算 $(7,10)$: 左辺 $10^2=100\equiv 1$、右辺 $7^3+2\cdot 7+7=364=11\cdot 33+1\equiv 1$。確かに $E$ 上の点である。

したがって $P+Q=(7,10)$。

まず $P$, $Q$ が $E$ 上にあることを確かめる。
- $P=(6,2)$: $6^3+2\cdot 6+7=235\equiv 4(\mathrm{mod}11)$、$y^2=4$ で一致する。
- $Q=(10,9)$: $10^3+2\cdot 10+7=1027\equiv 4(\mathrm{mod}11)$、$9^2=81\equiv 4$ で一致する。

$x_1\ne x_2$ なので、傾きは $\lambda =\frac{9-2}{10-6}=\frac{7}{4}$ である。${\mathbb{F}}_{11}$ では $4^{-1}=3$（$4\cdot 3=12\equiv 1$）だから、$\lambda \equiv 7\cdot 3=21\equiv 10\equiv -1$。

$x_3={\lambda }^2-x_1-x_2=1-6-10=-15\equiv 7(\mathrm{mod}11)$。

$y_3=\lambda (x_1-x_3)-y_1=(-1)(6-7)-2=-1\equiv 10(\mathrm{mod}11)$。

検算: $(7,10)$ について $7^3+2\cdot 7+7=364\equiv 1$、$10^2=100\equiv 1$ で $E$ 上にある。

よって $P+Q=(7,10)$。