Let $p$ be a large prime. Let $A$ be a $2\times 2$ matrix with coefficients in $GF(p)$ (i.e., coefficients taken modulo $p$). Let $B=A^k$, where $k$ is an integer not given to us. Given $p$, $A$, and $B$, the problem to find some $k$ such that $A^k=B$.

For which matrices $A$ does this problem have an efficient (poly-time) solution, and for which is it hard (say, as difficult as the discrete logarithm in $GF(p)$)?

I realize that for some choices of $A$ this problem can be solved efficiently. For others, it is as hard as the discrete log problem modulo $p$, for which there is no known poly-time algorithm. Can we somehow classify which matrices $A$ make this easy and which make it hard? I can work out the answer for some special cases but am having a hard time getting the overall picture.

In other words: When is there an efficient algorithm to solve the discrete logarithm problem, when working with $2\times 2$ matrices over $GF(p)$?

Follow-up question: is there a neat way to generalize from $2\times 2$ matrices to $n\times n$ matrices?

Start by putting $A$ into Jordan normal form, i.e., write $A=PJP^{-1}$ where $J$ is the Jordan normal form and $P$ is a suitably chosen invertible matrix. Then $A^k = PJ^k P^{-1}$, so without loss of generality I only need to consider possibilities for $A$ that are already in Jordan normal form.

For $2\times 2$ matrices, there are only three interesting cases:

1. Repeated eigenvalues: Suppose $$A = \begin{pmatrix} \lambda &1\\ 0 &\lambda \end{pmatrix}$$ where $\lambda \ne 0$. A simple induction shows that $$A^k = \begin{pmatrix} \lambda^k &k\lambda^{k-1}\\ 0 &\lambda^k \end{pmatrix}.$$ Therefore in this case, the problem is easy: $k = \lambda \times (k \lambda^{k-1}) / \lambda^k = A_{1,1} \times B_{1,2} /B_{1,1}$.

2. A zero eigenvalue: Suppose $$A = \begin{pmatrix} \lambda &0\\ 0 &0 \end{pmatrix}$$ where $\lambda$ is a generator modulo $p$ (i.e., it has order $p-1$ in the multiplicative group). Then this problem is exactly as hard as the discrete log problem to base $\lambda$ modulo $p$, i.e., it is unlikely to have a poly-time solution. This is because $$A^k = \begin{pmatrix} \lambda^k &0\\ 0 &0 \end{pmatrix},$$ so we have exactly an instance of the discrete log problem modulo $p$ hiding in there. If $\lambda$ is not a generator, the problem is exactly as hard as the discrete log to the base $\lambda$.

Note that this case is not in $GL(2,p)$, so strictly speaking it could be excluded from the case analysis, but I thought I'd show how to handle it.

3. Diagonal matrix: Suppose $$A = \begin{pmatrix} a &0\\ 0 &b \end{pmatrix}.$$ Then this problem is hard in general. For instance, if $a$ is a generator of $GF(p)$ and $b=1$, this problem is exactly as hard as the discrete log problem modulo $p$ (so most likely there is no polytime algorithm for it). If $a,b$ are both generators, then I believe the problem remains hard (see, e.g., this question), though I'm not aware of any reduction from the discrete log problem modulo $p$. If either $a$ or $b$ is such that the discrete log to base $a$ or $b$ is easy, then this problem is easy, though the chances of this happening by blind chance (if $a$ and $b$ are randomly chosen) is very low.

When we generalize to $n\times n$ matrices, I think the story remains approximately the same. If there is any Jordan block of size $>1$, then the discrete log problem is easy ($A^k$ contains the values $\lambda^k$ and $k \lambda^{k-1}$, so the same trick works). If $A$ is diagonal, then this is just an instance of this question; when the diagonal elements are chosen randomly, we can expect this to be hard (except with negligible probability).

• You should exclude the case of $\left[\begin{smallmatrix} a & 0 \\ 0 & 0 \end{smallmatrix}\right]$, as this matrix is not in $\mathrm{GL}(2,p)$. Sep 20 '12 at 10:10
• I think the Jordan normal form gives you a matrix with a=b, when the eigenvalues of the matrix actually exist. Can you just work over a degree 2 extension corresponding to the matrix's characteristic polynomial? If so, you have your characterization. Sep 20 '12 at 13:02