暗号理論の問題

手順 0：$m$ を決める。 $4^2=16<22\le 25=5^2$ なので $m=\lceil \sqrt{22}\rceil =5$ である。求める $x$ を $x=5i+j$（$0\le j<5$, $0\le i<5$）と表す。

手順 1：ベビーステップ（$5^j$ の表を作る）。 法 $23$ で
$$5^0\equiv 1,5^1\equiv 5,5^2=25\equiv 2,5^3\equiv 2\cdot 5=10,5^4\equiv 10\cdot 5=50\equiv 4.$$
よって表は $\{1(j=0),5(j=1),2(j=2),10(j=3),4(j=4)\}$。

手順 2：$g^{-m}=5^{-5}$ を求める。 $5^5\equiv 4\cdot 5=20(\mathrm{mod}23)$。$20^{-1}\mathrm{mod}23$ を拡張ユークリッドの互除法で求める。
$$23=1\cdot 20+3,20=6\cdot 3+2,3=1\cdot 2+1$$
を逆にたどると
$$1=3-2=3-(20-6\cdot 3)=7\cdot 3-20=7(23-20)-20=7\cdot 23-8\cdot 20.$$
よって $20^{-1}\equiv -8\equiv 15(\mathrm{mod}23)$（確認：$20\cdot 15=300=13\cdot 23+1$）。したがって $5^{-5}\equiv 15$。

手順 3：ジャイアントステップ（$21\cdot 15^i$ を表と照合）。
- $i=0$：$21$。表にない。
- $i=1$：$21\cdot 15=315=13\cdot 23+16\equiv 16$。表にない。
- $i=2$：$16\cdot 15=240=10\cdot 23+10\equiv 10$。表の $j=3$ と一致。

手順 4：$x$ を組み立てる。 $21\cdot (5^{-5}{)}^2\equiv 5^3$ より $21\equiv 5^{2\cdot 5+3}=5^{13}$。よって $x=2\cdot 5+3=13$。

検算： $5^{10}=(5^5{)}^2\equiv 20^2=400=17\cdot 23+9\equiv 9$、$5^{13}\equiv 9\cdot 5^3\equiv 9\cdot 10=90=3\cdot 23+21\equiv 21$。正しい。$5$ の位数は $22$ なので $0\le x\le 21$ の範囲で解はただ一つであり、$x=13$。

$m=\lceil \sqrt{22}\rceil =5$ とする。

【ベビーステップ】$5^j\mathrm{mod}23$ を $j=0,\dots ,4$ について求める。
$j=0:1,j=1:5,j=2:25\equiv 2,j=3:10,j=4:50\equiv 4$。

【ジャイアントステップ】$5^m=5^5\equiv 20$ である。$20\cdot 15=300=13\cdot 23+1$ より $5^{-5}\equiv 15(\mathrm{mod}23)$。
$21\cdot 15^i$ を $i=0,1,\dots$ について計算する。
- $i=0$: $21$。ベビーステップの表にない。
- $i=1$: $21\cdot 15=315\equiv 16$。表にない。
- $i=2$: $16\cdot 15=240\equiv 10$。表の $j=3$ に一致する。

よって $x=im+j=2\cdot 5+3=13$。

【検算】$5^{11}\equiv -1(\mathrm{mod}23)$ なので、$5^{13}=5^{11}\cdot 5^2\equiv -2\equiv 21$。確かに成り立つ。位数は 22 なので、$0\le x\le 21$ の範囲で解は一意である。