暗号理論の問題

手順 1：$m$ を決める。
$N=22$ であり、$4^2=16<22\le 25=5^2$ なので $m=\lceil \sqrt{22}\rceil =5$ である。求める $x$ は $x=im+j$（$0\le i<m,0\le j<m$）の形に書ける。

手順 2：ベビーステップの表を作る。
$5^j\mathrm{mod}23$（$0\le j\le 4$）を計算する。
$$5^0=1,5^1=5,5^2=25\equiv 2,5^3\equiv 2\cdot 5=10,5^4\equiv 10\cdot 5=50\equiv 4.$$
よって表は
$$j:0,1,2,3,4⟶5^j:1,5,2,10,4$$
となる。

手順 3：$g^{-m}=5^{-5}\mathrm{mod}23$ を求める。
$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$。

手順 4：ジャイアントステップで照合する。
$h(5^{-5}{)}^i=13\cdot 15^i\mathrm{mod}23$ を $i=0,1,2,\dots$ の順に計算し、表の値と一致するか調べる。
- $i=0$：$13$。表にない。
- $i=1$：$13\cdot 15=195=8\cdot 23+11\equiv 11$。表にない。
- $i=2$：$11\cdot 15=165=7\cdot 23+4\equiv 4$。表の $j=4$ と一致する。

手順 5：$x$ を求める。
$13\cdot (5^{-5}{)}^2\equiv 5^4$ より $13\equiv 5^{2\cdot 5+4}$ なので
$$x=im+j=2\cdot 5+4=14.$$

確認： $5^{14}=(5^5{)}^2\cdot 5^4\equiv 20^2\cdot 4=1600\equiv 1600-69\cdot 23=1600-1587=13(\mathrm{mod}23)$。正しい。

答え：$x=14$

$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=5\cdot 4=20(\mathrm{mod}23)$。$20\cdot 15=300=13\cdot 23+1$ より $20^{-1}\equiv 15(\mathrm{mod}23)$ である。そこで $13\cdot 15^i\mathrm{mod}23$ を $i=0,1,\dots$ について求める。
$i=0:13$ （表にない）。
$i=1:13\cdot 15=195=8\cdot 23+11\equiv 11$ （表にない）。
$i=2:11\cdot 15=165=7\cdot 23+4\equiv 4$ （表の $j=4$ と一致）。

よって $x=im+j=2\cdot 5+4=14$。

【検算】$5^{14}$ を順に計算する。$5^7\equiv 40\equiv 17$、$17^2=289=12\cdot 23+13\equiv 13$。よって $5^{14}\equiv 13(\mathrm{mod}23)$ となり条件を満たす。$0\le x\le 21$ の範囲で $5$ の位数が $22$ なので解は一意である。