暗号理論の問題

手順1：指数を2進法で表す。

$19=16+2+1$ なので、$19=10011_{(2)}$ である。よって
$$3^{19}=3^{16}\cdot 3^2\cdot 3^1$$
と分解できる。

手順2：$3^{2^k}\mathrm{mod}43$ を、前の値を2乗して順に求める。

各段階で $43$ で割った余りに置き換えてから2乗する。

• $3^1\equiv 3$
• $3^2\equiv 3^2=9$
• $3^4\equiv 9^2=81=43\cdot 1+38$ より $3^4\equiv 38$
• $3^8\equiv 38^2=1444=43\cdot 33+25$ より $3^8\equiv 25$
• $3^{16}\equiv 25^2=625=43\cdot 14+23$ より $3^{16}\equiv 23$

（すべて $(\mathrm{mod}43)$）

手順3：2進法で1が立っている桁に対応するものを掛け合わせる。

$$3^{19}\equiv 3^{16}\cdot 3^2\cdot 3^1\equiv 23\cdot 9\cdot 3=23\cdot 27=621(\mathrm{mod}43)$$

$621=43\cdot 14+19$ なので
$$3^{19}\equiv 19(\mathrm{mod}43)$$

検算： $3^{20}\equiv 3^{16}\cdot 3^4\equiv 23\cdot 38=874=43\cdot 20+14$ より $3^{20}\equiv 14$ である。一方、$3^{19}\cdot 3\equiv 19\cdot 3=57\equiv 14$ となり、一致する。

よって $r=19$ である。

$19=16+2+1$ なので、$3^{2^k}$ を順に $43$ で割った余りで求める。
$3^1\equiv 3$
$3^2\equiv 9$
$3^4\equiv 81\equiv 81-43=38$
$3^8\equiv 38^2=1444=43\cdot 33+25\equiv 25$
$3^{16}\equiv 25^2=625=43\cdot 14+23\equiv 23$
よって $3^{19}=3^{16}\cdot 3^2\cdot 3\equiv 23\cdot 9\cdot 3=23\cdot 27=621=43\cdot 14+19\equiv 19$。
検算: $3^{19}=1162261467=43\cdot 27029336+19$ となり、余りは $19$ で一致する。