暗号理論の問題

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

$$13=8+4+1=1101_{(2)}$$

したがって $7^{13}=7^8\cdot 7^4\cdot 7^1$ である。

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

• $7^1\equiv 7(\mathrm{mod}61)$
• $7^2=49$ なので $7^2\equiv 49(\mathrm{mod}61)$
• $7^4=(7^2{)}^2\equiv 49^2=2401$ である。$2401=61\times 39+22$ より $7^4\equiv 22(\mathrm{mod}61)$
• $7^8=(7^4{)}^2\equiv 22^2=484$ である。$484=61\times 7+57$ より $7^8\equiv 57(\mathrm{mod}61)$

手順 3：2 進法で 1 が立つ桁（$2^3,2^2,2^0$）の値を掛け合わせる。

掛けるたびに $61$ で割った余りに直す。

$$7^8\cdot 7^4\equiv 57\times 22=1254$$

$1254=61\times 20+34$ より、この積は $34$ と合同である。続けて $7^1$ を掛けると

$$34\times 7=238$$

$238=61\times 3+55$ より

$$7^{13}\equiv 55(\mathrm{mod}61)$$

検算： $57\equiv -4(\mathrm{mod}61)$ を使うと、$7^{13}\equiv (-4)\times 22\times 7=-616$ となる。$616=61\times 10+6$ なので $-616\equiv -6\equiv 55(\mathrm{mod}61)$ となり、結果は一致する。

よって求める余りは $55$ である。

13 = 1101（2進）なので 7^13 = 7^8 · 7^4 · 7^1。mod 61 で繰り返し二乗する。
7^1 = 7。
7^2 = 49。
7^4 = 49^2 = 2401。61·39 = 2379 なので 2401 − 2379 = 22。よって 7^4 ≡ 22。
7^8 ≡ 22^2 = 484。61·7 = 427 なので 484 − 427 = 57 ≡ −4。よって 7^8 ≡ 57。
したがって 7^13 ≡ 7^8 · 7^4 · 7 ≡ (−4)·22·7 = −616。
616 = 61·10 + 6 なので −616 ≡ −6 ≡ 55 (mod 61)。
検算：フェルマーの小定理より 7^60 ≡ 1。別の方法として 7^3 = 343 = 61·5 + 38 なので 7^3 ≡ 38。7^6 ≡ 38^2 = 1444 = 61·23 + 41 なので 41。7^12 ≡ 41^2 = 1681 = 61·27 + 34 なので 34。7^13 ≡ 34·7 = 238 = 61·3 + 55 なので 55。一致する。