暗号理論の問題

原始根 $g=5$ を使い、法 $23$ の離散対数（指数）${\mathrm{ind}}_5$ で合同式を $1$ 次の合同式に直す。

1. $5$ のべきの表を作る。 法 $23$ で前の値に $5$ を掛けていくと
$$\begin{array}{ccccccccccccc}k& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11\\ 5^k& 1& 5& 2& 10& 4& 20& 8& 17& 16& 11& 9& 22\end{array}$$
$$\begin{array}{cccccccccccc}k& 12& 13& 14& 15& 16& 17& 18& 19& 20& 21& 22\\ 5^k& 18& 21& 13& 19& 3& 15& 6& 7& 12& 14& 1\end{array}$$
となる（例: $5^6=5^5\cdot 5\equiv 20\cdot 5=100=92+8\equiv 8$）。表から ${\mathrm{ind}}_{5}7=19$、つまり $5^{19}\equiv 7(\mathrm{mod}23)$ である。

2. 指数の合同式に直す。 $1\le x\le 22$ の $x$ は $23$ と互いに素なので、$x\equiv 5^y$ となる $0\le y\le 21$ がただ $1$ つある。すると $x^5\equiv 5^{5y}$ であり、$5$ の位数が $22$ なので
$$5^{5y}\equiv 5^{19}(\mathrm{mod}23)⟺5y\equiv 19(\mathrm{mod}22).$$

3. $1$ 次合同式を解く。 $\gcd (5,22)=1$ なので解はただ $1$ つ。$5\cdot 9=45=2\cdot 22+1$ より $5^{-1}\equiv 9(\mathrm{mod}22)$。よって
$$y\equiv 9\cdot 19=171=7\cdot 22+17\equiv 17(\mathrm{mod}22).$$
表から $x\equiv 5^{17}\equiv 15(\mathrm{mod}23)$。

4. 確かめ。 $15^2=225=9\cdot 23+18\equiv 18$、$15^4\equiv 18^2=324=14\cdot 23+2\equiv 2$、$15^5\equiv 2\cdot 15=30\equiv 7(\mathrm{mod}23)$。

したがって $x=15$。

$\gcd (5,22)=1$ なので、写像 $x\mapsto x^5$ は $(\mathbb{Z}/23{)}^{\times }$ 上の全単射。$5d\equiv 1(\mathrm{mod}22)$ を満たす $d$ を求めると $5\cdot 9=45=2\cdot 22+1$ より $d=9$。このとき $x\equiv (x^5{)}^9=7^9$ （$x^{45}=x^{44}\cdot x=x$、フェルマーの小定理）。\n\n$7^2=49\equiv 3$, $7^4\equiv 9$, $7^8\equiv 81\equiv 12$, $7^9\equiv 12\cdot 7=84\equiv 84-69=15(\mathrm{mod}23)$。よって $x=15$。\n\n検算: $15^2=225\equiv 225-207=18$, $15^4\equiv 18^2=324\equiv 324-322=2$, $15^5\equiv 2\cdot 15=30\equiv 7(\mathrm{mod}23)$ ✓。