yukicoder No.950 行列累乗 解説
$ A := \begin{pmatrix} a & b \\ c & d \end{pmatrix}とする。
$ J = SAS^{-1}としてジョルダン標準形にする。
(i)$ Jが対角化可能なとき、$ J := \begin{pmatrix} \alpha & 0 \\ 0 & \beta \end{pmatrix}とおける。
$ J^n = \begin{pmatrix} \alpha^n & 0 \\ 0 & \beta^n \end{pmatrix} = S^{-1}BS \bmod p
を$ nについて解けばよい。$ S^{-1}BS=\begin{pmatrix} u & 0 \\ 0 & v \end{pmatrix}と書ける必要があって、非対角成分が非零なら解なし。
$ d:=(a+d)^2-4(ad-bc)とすれば、固有値$ \alpha,\beta=$ \frac{1}{2}\left(a+d \pm \sqrt{d} \right)となるから、$ \mathbb{Z} \lbrack\sqrt{d}\rbrack / p\mathbb{Z}\lbrack\sqrt{d}\rbrack上で
離散対数問題$ \alpha^n = u \bmod p\land \beta^n = v \bmod pを解けばいい。ノルム$ N(\alpha):=\alpha\bar{\alpha}を先にそろえよう。$ N(\alpha)\in\mathbb{Z}/p\mathbb{Z}
だから、元の個数は$ p-1個である。従って、ノルム写像が準同型写像であることを用いて$ O(\sqrt{p}\log{p})で$ N(\alpha^x)=N(u)なる$ xが計算できる。$ N(\alpha)の位数$ \mathrm{ord}(N(\alpha))も求めておく。両辺のノルムが等しいことから、ある整数$ kを用いて$ n = x+\mathrm{ord}(N(\alpha))kと書ける。フロベニウス写像より任意の$ rについて$ r^p = \bar{r}だから、$ r^{p+1}=N(r)となる。$ r=\alpha^{\mathrm{ord}(N(\alpha))}とすると、$ N(r)=1だから、$ rを生成元とする巡回群の位数は$ p+1以下。よって同様に離散対数問題として$ O(\sqrt{p}\log{p})で解くことが出来る。$ \alpha^n = u \bmod p, \beta^n = v \bmod pの解をそれぞれ$ s_1,s_2とすれば、
$ (s_1+\mathrm{ord}(\alpha)\mathbb{Z}) \cap (s_2+\mathrm{ord}(\beta)\mathbb{Z})で表される最小の正整数が$ nになる。これは拡張ユークリッドの互除法で解くことが出来る。
(ii)$ Jが対角化可能でないとき、$ J := \begin{pmatrix} \alpha & 1 \\ 0 & \alpha \end{pmatrix}とおける。
$ J^n =\begin{pmatrix} \alpha^n & n\alpha^{n-1} \\ 0 & \alpha^n \end{pmatrix}= S^{-1}BS \bmod p
となるから、対角成分が合致する場合を(i)と同様にして求める。そのような$ nを$ mと置く。すると、(1,2)成分があとは等しくなれば良い。ある整数$ kを用いて$ n:=m+k\mathrm{ord}(\alpha)と置ける。このとき
$ J^{n+k\mathrm{ord}(\alpha)} =\begin{pmatrix} \alpha^m & (m+k\mathrm{ord}(\alpha))\alpha^{m-1} \\ 0 & \alpha^m \end{pmatrix}= S^{-1}BS \bmod p
だから、$ k=(\mathrm{ord(\alpha)})^{-1}((S^{-1}BS)_{1,2} \alpha^{1-m}-m)となり解は必ず存在する。
余談だが、$ N(\alpha)=1 \Leftrightarrow \mathrm{det}(\alpha) だから、$ \mathrm{det}(A)=1ならば(i)では周期は$ p+1以下、(ii)では周期は$ 2p,p,2,1のいずれかであることが分かる。