Can I find the exponent of a matrix given only a vector and its image?

Question

here is my problem :

Given a $GL(m,2)$ matrix $A$, and $x,y$ two non-zero $F_2$ vectors of length $m$ with the premise that $y = x(A^n)$ for some positive integer $n$. The goal is to find n.

Is it possible without computing all $xA^i$ until $n$ is found? If not, it is possible with a quantum computer ?

I know that Shor's algorithm allows to find $n$ given $A$ and $A^n$, but what if instead of $A^n$, only a pair vector-image is given ?

Thank you for any help

Answer 1

If $A$ is diagonalizable, $A=PDP^{-1}$ for some invertible $P$ and some diagonal $D$, then $yP=(xP)D^n$, and now it's easy to get $n$.

Even if $A$ is not diagonalizable, its Jordan form $J$ is simple enough that it should be possible to recover $n$ from $yP=(xP)J^n$.

Answer 2

In my opinion, your question is not obvious to solve. About the Gerry's answer, it's true that $A$ is (in general) diagonalizable but, how do you diagonalize $A$ over $F_2$ ? Note that you need $P,D$;

step 1. With Berlekamp, you can decompose $\chi_A$ in product of irreducible.

step 2. -For each irreducible- you can write the roots of this factor as explicit polynomials of a particular root (noted $\alpha$).

step 3. You calculate the associated eigenvectors as polynomial functions of the $\alpha$...

I tested that with Maple; when $m=10$, I got nothing in 10'. However it works quickly for $m=6$. What is $m$ for the OP? As he is fond of quantum computation, perhaps $m=1000$... Perhaps also Magma has a software dedicated to this kind of calculation.

Note that necessarily $n\leq 2^m$. Then, if you test the $xA^k-y$, you can obtain the result with complexity in $O(2^mm^2)$.

EDIT. Unfortunately, when $A$ is randomly chosen in $M_{100}(F_2)$, $70$% of these matrices have at least one multiple eigenvalue; multiple factors of $\chi_A$ are almost always $x,x+1$ or $x^2+x+1$. Note also that a random matrix with a multiple eigenvalue is almost always non-diagonalizble.

In your problem, there are $2$ parts.

PART 1. Jordan form of $A$.

I wrote a procedure that diagonalizes the $A\in M_m(F_2)$ that have only simple eigenvalues. Note that this only covers $30$% of cases.

I think that the complexity of the calculation of $P,D$ is $O(m^5)$. To give an idea, during a test, with $m=10$, the calculation time was $1"26$ and, with $m=20$, the calculation time was $50"8$. Finally, for $m=100$, it would take almost $2$ days of calculation. It is true that there are softwares that are faster than Maple.

PART 2. It remains to solve a system of $m$ equations, in the unknown $n$, in the form

$a_i^n=b_i,i=1,\cdots,m$, where $a_i,b_i$ are in algebraic extensions of $F_2$. Here, you must work about discrete $\log$.