暗号理論の問題

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

手順 2：ベビーステップの表を作る。 $5^j\mathrm{mod}23$（$0\le j<5$）を計算します。
$$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.$$
よって表は $\{1\mapsto 0,5\mapsto 1,2\mapsto 2,10\mapsto 3,4\mapsto 4\}$ です。

手順 3：$g^{-m}$ を求める。 $5^5\equiv 4\cdot 5=20(\mathrm{mod}23)$ です。$20^{-1}\mathrm{mod}23$ を求めます。$20\equiv -3$ で、$3\cdot 8=24\equiv 1$ より $3^{-1}\equiv 8$、したがって $(-3{)}^{-1}\equiv -8\equiv 15$ です。確かめると $20\cdot 15=300=23\cdot 13+1$ です。よって $g^{-m}=5^{-5}\equiv 15$。

手順 4：ジャイアントステップで照合する。 $h=21$ から始めて $15$ を掛けていき、表にあるかを調べます。
- $i=0$：$21$ は表にない。
- $i=1$：$21\cdot 15=315=23\cdot 13+16$ より $16$。表にない。
- $i=2$：$16\cdot 15=240=23\cdot 10+10$ より $10$。表にあり、$j=3$。

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

検算： $5^{13}=5^{10}\cdot 5^3$ で、$5^5\equiv 20\equiv -3$ より $5^{10}\equiv 9$、$9\cdot 10=90=23\cdot 3+21\equiv 21$。正しいです。

答え：$x=13$

法 23 で $m=\lceil \sqrt{22}\rceil =5$ とおき、$x=im+j$（$0\le i,j<5$）の形で探す。

ベビーステップ（$5^j\mathrm{mod}23$, $j=0,\dots ,4$）：$1,5,2,10,4$。

ジャイアントステップ：$5^5=3125\equiv 20(\mathrm{mod}23)$ であり、$20\cdot 15=300\equiv 1$ より $5^{-5}\equiv 15$。そこで $21\cdot 15^i$ を順に計算する。
- $i=0$: $21$（ベビーステップの表にない）
- $i=1$: $21\cdot 15=315\equiv 16$（表にない）
- $i=2$: $16\cdot 15=240\equiv 10$（表の $j=3$ と一致）

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

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