<p>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.</p>

<p>For $2\times 2$ matrices, there are only three interesting cases:</p>

<ol>
<li><p><strong>Repeated eigenvalues:</strong> Suppose
$$A = \begin{pmatrix} \lambda &amp;1\\ 0 &amp;\lambda \end{pmatrix}$$
where $\lambda \ne 0$.  A simple induction shows that
$$A^k = \begin{pmatrix} \lambda^k &amp;k\lambda^{k-1}\\ 0 &amp;\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}$. </p></li>
<li><p><strong>A zero eigenvalue:</strong> Suppose
$$A = \begin{pmatrix} \lambda &amp;0\\ 0 &amp;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 &amp;0\\ 0 &amp;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$.</p>

<p>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. </p></li>
<li><p><strong>Diagonal matrix:</strong> Suppose
$$A = \begin{pmatrix} a &amp;0\\ 0 &amp;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., <a href="https://crypto.stackexchange.com/q/3837/351">this question</a>), 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.</p></li>
</ol>

<p>When we generalize to $n\times n$ matrices, I <em>think</em> the story remains approximately the same.    If there is any Jordan block of size $&gt;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 <a href="https://crypto.stackexchange.com/q/3837/351">this question</a>; when the diagonal elements are chosen randomly, we can expect this to be hard (except with negligible probability).</p>

CC BY-SA 3.0
2012-09-20T10:10:56.350Z
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)$.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-20T13:02:22.987Z
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.
Adam Smith
CC BY-SA 3.0
2012-09-19T18:34:37.997Z
2012-10-24T02:35:42.380Z
2017-04-13T12:48:17.970Z
D.W.
<p>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$.</p>

<p>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)$)?</p>

<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.</p>

<p>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)$?</p>

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

<cr.crypto-security><matrices><nt.number-theory><comp-number-theory>
Discrete log in GL(2,p)
D.W.
# Discrete log in GL(2,p)

(Asked by: username_0 on 2012-09-19)

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?

**Tags:** cr.crypto-security, matrices, nt.number-theory, comp-number-theory

---

## 1 answers

### Answer by username_0 on 2012-09-19. Score: 6 | Accepted answer

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](https://crypto.stackexchange.com/q/3837/351)), 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](https://crypto.stackexchange.com/q/3837/351); when the diagonal elements are chosen randomly, we can expect this to be hard (except with negligible probability).

> **Comments:**
> **username_1**: 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)$.  
> **username_2**: 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.  

---

