# 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, 2012 at 6:04
• You may want to consider asking this question at cstheory.SE (check the cross-listing policy first). Sep 21, 2012 at 5: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 $$P^{-1}x=(x_1, x_2)$$ and $$P^{-1}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)/y_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. Oct 24, 2012 at 12:57
• Oh, right! Good point, @ThomasPornin. I've edited the answer to point this out. Thank you.
– D.W.
Oct 24, 2012 at 16:41
• Note that "easy" recovery only gives $k \mod p$. For a full-size $k$, no easy solution it seems. Even worse, JNF does not always exist over GF(p), we may need to consider a field extension and do discrete log there. Jul 21, 2021 at 6:49
• @Fractalice, oh gosh. Sounds like my answer is completely wrong, then. Thank you so much for explaining that to me. Would you recommend that I delete this answer? Might you be able to provide an answer?
– D.W.
Jul 21, 2021 at 20:51
• @D.W. No, I would just suggest to add that the JNF may require considering the matrix over the extension field $GF(p^k)$ (where all the eigenvalues exist). Each eigenvalue can be considered separately (leading to a discrete log instance in the field where the eigenvalue lives). And that the "easy" trick only reveals the solution mod p (besides the discrete log part). I think as long as length of each Jordan block is at most p, this is actually complete, i.e. we can recover full discrete log in this way. Jul 22, 2021 at 11:34