ARC194E - Swap 0^X and 1^Y、ハッシュ解法
問題
略解
群 $ G を $ G := \langle 0, 1 \mid 0^X 1^Y = 1^Y 0^X \rangle と定める（群の表示）．行列 $ A, B で等式 $ A^X B^Y = B^Y A^X を満たすものをランダムに選び， $ A, B で生成される群 $ H = \langle A, B \rangle を作る． $ f: G \to H, f(0) = A, f(1) = B なる準同型をとり， $ f(S) = f(T) なら Yes，さもなくば No とすればよい．
問題は $ A, B の選び方で，変な選び方をすると $ AB = BA のような低次の関係式が成り立ってハッシュとして使い物にならない．行列の積が交換可能 $ \iff 同時対角化可能などの線形代数の知識を使って良い行列を用意する．説明は難しいので例示すると，
$ A = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} \cos(\frac{\pi}{5}) & -\sin(\frac{\pi}{5}) & 0 \\ \sin(\frac{\pi}{5}) & \cos(\frac{\pi}{5}) & 0 \\ 0 & 0 & 314 \end{pmatrix} \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}^{-1}
$ B = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 159 & 0 & 0 \\ 0 & \cos(\frac{\pi}{3}) & -\sin(\frac{\pi}{3}) \\ 0 & \sin(\frac{\pi}{3}) & \cos(\frac{\pi}{3}) \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} ^{-1}
とすれば
$ A B - B A = \begin{pmatrix} 0 & 185.31 & 2.03615 \\ 92.6549 & 0 & 543.481 \\ -0.509037 & 271.74 & 0 \end{pmatrix} \neq \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}
$ A^5 B^3 - B^5 A^3 = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}
となる．これを適切な有限体 $ \mathbb{F}_p 上でやればいい．
提出
元ポスト