暗号理論の問題

手順 1：指数を 2 進法で表す。
$13=8+4+1=2^3+2^2+2^0$ なので、$13=1101_{(2)}$ である。したがって
$$7^{13}=7^8\cdot 7^4\cdot 7^1$$
となり、$7^1,7^2,7^4,7^8$ を法 $53$ で求めればよい。

手順 2：順に 2 乗して $7^{2^k}\mathrm{mod}53$ を求める。（毎回 $53$ で割った余りに直してから次の 2 乗をする）
- $7^1\equiv 7$
- $7^2=49$ なので $7^2\equiv 49(\mathrm{mod}53)$
- $7^4=(7^2{)}^2\equiv 49^2=2401$。$53\times 45=2385$ より $2401-2385=16$ なので $7^4\equiv 16(\mathrm{mod}53)$
- $7^8=(7^4{)}^2\equiv 16^2=256$。$53\times 4=212$ より $256-212=44$ なので $7^8\equiv 44(\mathrm{mod}53)$

手順 3：2 進法で 1 の立つ桁のものを掛け合わせる。
$$7^{13}=7^8\cdot 7^4\cdot 7\equiv 44\cdot 16\cdot 7(\mathrm{mod}53)$$
まず $44\cdot 16=704$。$53\times 13=689$ より $704-689=15$ なので $44\cdot 16\equiv 15$。
次に $15\cdot 7=105$。$105-53=52$ なので $15\cdot 7\equiv 52$。

よって $7^{13}\equiv 52(\mathrm{mod}53)$ であり、$r=52$ である。

（確認：$52\equiv -1(\mathrm{mod}53)$ であり、$7^2\equiv -4$, $7^4\equiv 16$, $7^8\equiv -9$ と負の代表を使うと $7^{13}\equiv (-9)\cdot 16\cdot 7=-1008$、$-1008+53\times 19=-1008+1007=-1$ となり一致する。）

繰り返し二乗法で $7^{13}$ を $53$ で割った余りを求める。$13=8+4+1$ より $7^{13}=7^8\cdot 7^4\cdot 7$ と分ける。

• $7^1\equiv 7$
• $7^2=49\equiv -4$
• $7^4\equiv (-4{)}^2=16$
• $7^8\equiv 16^2=256=53\cdot 4+44\equiv 44$

よって
$7^{13}\equiv 44\cdot 16\cdot 7(\mathrm{mod}53)$。

$44\cdot 16=704=53\cdot 13+15$ より $44\cdot 16\equiv 15$。
$15\cdot 7=105=53\cdot 1+52$ より $15\cdot 7\equiv 52$。

したがって $r=52$（$\equiv -1$）。

検算：$7^{12}=(7^4{)}^3\equiv 16^3=4096=53\cdot 77+15\equiv 15$。$7^{13}\equiv 15\cdot 7=105\equiv 52$。一致する。