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?
Discrete log in GL(2,p)
cr.crypto security;matrices;nt.number theory;comp number theory
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: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}$. 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 discretelog 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. 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).