7
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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).

$\endgroup$
  • 4
    $\begingroup$ 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)$. $\endgroup$ – Niel de Beaudrap Sep 20 '12 at 10:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Adam Smith Sep 20 '12 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.