# A discrete-log-like problem, with matrices: given $A^k x$, find $k$

Let $p$ be a large prime; we will work in $GF(p)$. Let $A$ be a $n\times n$ matrix. Also, let $x$ be a $n$-vector and $k$ a positive integer.

Suppose we are given $p$, $A$, $x$, and $y$. The goal is to find a $k$ that satisfies $A^k x = y$. Is there an efficient algorithm that solves this problem? You can assume you are promised that at least one solution exists, if you want.

More generally, what is the complexity of this problem? How does its hardness relate to the hardness of the standard discrete log problem modulo $p$? I'm pretty sure the answer will depend upon the matrix $A$. Can we classify for which matrices $A$ this is as hard as the standard discrete log problem, for which it is harder, for which it is easier, for which it can be solved in polynomial time?

-
If you could solve that problem for any matrix A, you could solve the DL mod p problem; and also that other problem of yours, I think. –  fgrieu Sep 20 '12 at 6:04
You may want to consider asking this question at cstheory.SE (check the cross-listing policy first). –  Mikero Sep 21 '12 at 5:18
Thanks for the edit, @bob! Good catch. –  D.W. Oct 24 '12 at 20:18

The answer appears to be similar to one that I asked on cstheory.SE about Discrete log in GL(2,p) (i.e., given $A,B$, find $k$ such that $A^k=B$). In this question we are given less information, but similar techniques should still apply.

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. This means that $A$ can be expressed as a concatenation of Jordan blocks: $$A = \begin{pmatrix} J_1 \\&\ddots\\ &&J_n\end{pmatrix}.$$

Each Jordan block gives us an independent system of equations, so let me look at a single Jordan block at a time. We can break this down into cases, based upon the size of the Jordan block $J$:

1. A size-1 Jordan block. Suppose $J$ is a $1\times 1$ Jordan block, i.e., $$J=\begin{pmatrix} \lambda \end{pmatrix}.$$ Then it is easy to see that the problem is exactly as hard as the discrete log to base $\lambda$ (unless $x=0$ in this component, in which case it is unsolvable for information-theoretic reasons).

2. A size-2 Jordan block. Suppose $J$ is a $2\times 2$ Jordan block, i.e., $$J = \begin{pmatrix} \lambda &1\\ 0 &\lambda \end{pmatrix}$$ where $\lambda \ne 0$. A simple induction shows that $$J^k = \begin{pmatrix} \lambda^k &k\lambda^{k-1}\\ 0 &\lambda^k \end{pmatrix}.$$ Let $x=(x_1, x_2)$ and $y=(y_1, y_2)$. Then we obtain the linear equations \begin{align*} \lambda^k x_1 + k\lambda^{k-1} x_2 &= y_1\\ \lambda^k x_2 &= y_2 \end{align*} which has the solution $$k = \lambda (y_1 - x_1 y_2/x_2)/x_2.$$ We see that as long as $x_2 \ne 0$, the problem is easy and we can solve for $k$ with a little bit of arithmetic (no discrete log needed). If $x_2=0$, I'd conjecture that this case is hard.

3. A larger Jordan block. If we have a larger Jordan block, say $m \times m$, basically the same thing happens. The top row of $J^k$ is $(\lambda^k, k \lambda^{k-1}, {k \choose 2} \lambda^{k-2}, \dots)$, and each subsequent row is a right-shift of the one before it. Then, as long as $(x_2,x_3,\dots,x_m) \ne (0,0,\dots,0)$, we can solve for $k$ easily as in the $2\times 2$ case.

So, each Jordan block gives us a chance to solve for $k$. If any of the Jordan blocks are easy, we learn $k$. If all of the Jordan blocks are hard, learning $k$ is hard.

In summary: If the Jordan normal form of $A$ is diagonal, and at least one of the diagonal elements is such that discrete log to that base is hard, then this problem is as hard as the discrete log. On the other hand, if the Jordan normal form is not diagonal---i.e., if it has at least one Jordan block of size $>1$---then the problem is easy (except in corner cases where the wrong components of $x$ happens to be zero).

-
In the $m\times m$ case, you just need one of the $x_j$ for $1 \lt j \leq m$ to be non-zero, to solve for $k$. To make it hard (i.e. equivalent to DL), all of the $x_j$ (except $x_1$) must be zero. –  Thomas Pornin Oct 24 '12 at 12:57
Oh, right! Good point, @ThomasPornin. I've edited the answer to point this out. Thank you. –  D.W. Oct 24 '12 at 16:41