暗号理論の問題

合成写像の形 二重暗号化では、位置 $j$（$0\le j\le 17$）の文字は
$$x_j⟼x_j+k_{j\mathrm{mod}6}+l_{j\mathrm{mod}9}(\mathrm{mod}26)$$
と変換される。つまり合成写像は、ずらし量の列
$$s_j=k_{j\mathrm{mod}6}+l_{j\mathrm{mod}9}(0\le j\le 17)$$
を持つ「長さ $18$ の鍵のヴィジュネル暗号」と同じである。

ずらし量の列 $(s_0,\dots ,s_{17})$ が異なれば、写像も異なる。実際、$s_j\ne s_j^{\prime }$ となる $j$ があれば、すべて $\mathrm{A}=0$ からなる平文の第 $j$ 文字の行き先が違う。したがって、求める写像の個数は、写像
$$\phi :(\mathbb{Z}/26\mathbb{Z}{)}^6\times (\mathbb{Z}/26\mathbb{Z}{)}^9\to (\mathbb{Z}/26\mathbb{Z}{)}^{18},(K,L)\mapsto (s_0,\dots ,s_{17})$$
の像の元の個数に等しい。$\phi$ は加法群の準同型なので、準同型定理から
$$|\mathrm{Im}\phi |=\frac{26^{15}}{|\mathrm{Ker}\phi |}.$$

核の計算 $(K,L)\in \mathrm{Ker}\phi$ となる条件は、すべての $j$（$0\le j\le 17$）について
$$k_{j\mathrm{mod}6}+l_{j\mathrm{mod}9}\equiv 0(\mathrm{mod}26)$$
が成り立つことである。

まず、$j$ が $0\le j\le 17$ を動くとき、どんな組 $(r,s)=(j\mathrm{mod}6,j\mathrm{mod}9)$ が現れるかを調べる。$\gcd (6,9)=3$ なので、連立合同式 $j\equiv r(\mathrm{mod}6)$, $j\equiv s(\mathrm{mod}9)$ が解をもつのは $r\equiv s(\mathrm{mod}3)$ のときに限る（一般化した中国剰余定理）。そのとき解は法 $\mathrm{lcm}(6,9)=18$ でただ一つ定まる。条件 $r\equiv s(\mathrm{mod}3)$ を満たす組は $6\times 3=18$ 個あり、$j$ の個数 $18$ と一致するので、これらの組はちょうど $1$ 回ずつ現れる。

よって核の条件は
$$k_r\equiv -l_s(\mathrm{mod}26)(r\equiv s(\mathrm{mod}3)\text{ を満たすすべての }0\le r\le 5,0\le s\le 8)$$
である。各 $t\in \{0,1,2\}$ について、$r\in \{t,t+3\}$ と $s\in \{t,t+3,t+6\}$ のすべての組でこの式が成り立つ。したがって、ある $c_t$ を用いて
$$k_t=k_{t+3}=c_t,l_t=l_{t+3}=l_{t+6}=-c_t$$
と書けることが必要十分である。$c_0,c_1,c_2$ はそれぞれ $26$ 通りを自由にとれるので
$$|\mathrm{Ker}\phi |=26^3.$$

結論
$$|\mathrm{Im}\phi |=\frac{26^{15}}{26^3}=26^{12}(=95428956661682176).$$

したがって、二重暗号化で得られる写像は $26^{12}$ 通りである。

二重暗号化は $x_j\mapsto x_j+k_{j\mathrm{mod}6}+l_{j\mathrm{mod}9}$ であり、写像は加えるシフトベクトル $v_j=k_{j\mathrm{mod}6}+l_{j\mathrm{mod}9}$ ($j=0,\dots ,17$) だけで決まる。したがって、異なる写像の数は、線形写像 $\Phi :(K,L)\mapsto v$ ($(\mathbb{Z}/26{)}^{15}\to (\mathbb{Z}/26{)}^{18}$) の像の元の個数に等しい。

像の大きさは $26^{15}/|\ker \Phi |$ である。そこで核を求める。

$\ker \Phi$ の元は、すべての $j=0,\dots ,17$ について $k_{j\mathrm{mod}6}+l_{j\mathrm{mod}9}=0$ を満たす。

$\gcd (6,9)=3$、$\mathrm{lcm}(6,9)=18$ なので、中国剰余定理より $j=0,\dots ,17$ は組 $(a,b)=(j\mathrm{mod}6,j\mathrm{mod}9)$ のうち $a\equiv b(\mathrm{mod}3)$ をみたすもの（$18$ 通り）をちょうど一度ずつ取る。よって条件は、$a\equiv b(\mathrm{mod}3)$ をみたすすべての $(a,b)$ について $k_a=-l_b$ となることである。

各剰余 $r\in \{0,1,2\}$ について、$a\equiv r$ の $k_a$ は $2$ 個、$b\equiv r$ の $l_b$ は $3$ 個ある。これらは完全二部グラフ状につながるので、$k_a=c_r$（すべての $a\equiv r$）、$l_b=-c_r$（すべての $b\equiv r$）となる。

自由なパラメータは $c_0,c_1,c_2$ の $3$ 個なので、$|\ker \Phi |=26^3$ である。

ゆえに写像の個数は $26^{15}/26^3=26^{12}$。

検算：像の次元（$\mathbb{Z}/26$ 上の自由加群として）は $15-3=12$。直感的にも、定数 $c_r$ を $K$ に足し $L$ から引く冗長性が $3$ 個あるので整合する。