1

Is there an efficient method to compute the order of a matrix $M$ of size $n \times n$ with elements from $GF(2)$ for large (=32,64,128) $n$? I.e. compute the smallest $i$ such that $M^i = I$.

I've found some related questions:

This one says

If the matrix isn't diagonalizable, or if it has an eigenvalue that is not a root of unity, then its order is infinite. Otherwise, the order of the matrix is the LCM of the orders of the roots of unity.

I presume the order of my matrix can't be infinite (since its elements are from $GF(2)$), so I presume the second sentence would answer my question. Unfortunately, I don't understand what exactly is meant. Why would the order of a matrix be the lcm of something that is independent of the matrix? Or does the author mean the lcm of the order of the eigenvalues? In any case I don't understand the relationship between these concepts or why they would give me the answer to my problem.

Here's some more related questions that don't really answer my question:

My motivation is the xorshift128+ pseudorandom number generator, which uses linear transformations and claim sto have a period of $2^{128}-1$, but I could not find a proof or method how they obtained the order of the transformations.

Thanks a lot in advance!

Ben Grossmann
  • 225,327
ambiso
  • 111
  • 2
    Regarding the quote: the idea is that if $M$ is diagonalizable and every eigenvalue of $M$ is a root of unity, then the order of $M$ will be the LCM of the orders of the eigenvalues (which are roots of unity). – Ben Grossmann Jul 19 '20 at 10:13
  • 2
    One approach would be to first find the minimal polynomial of $M$ (with coefficients in $GF(2)$). If $M$ has minimal polynomial $p(x)$, then your question is equivalent to finding the smallest $k$ such that $p(x) \mid x^k - 1$. – Ben Grossmann Jul 19 '20 at 10:23
  • 1
    A possibly helpful observation: if $M$ is diagonalizable over the appropriate field extension, then it necessarily holds that $p(x) \mid x^{2^n - 1} - 1$. In other words, $M$ has order at most $2^n - 1$, and the order of $M$ necessarily divides $2^n - 1$ (in this case). Fortunately, numbers of the form $2^n - 1$ can be factored with relative efficiency. – Ben Grossmann Jul 19 '20 at 10:41
  • To be a bit more specific, these order-$128$ matrices are obtained by selecting suitable $a,b,c$ and taking the matrix $$ M = \pmatrix{0&0&0&(I + L^a)(I + R^b)\ I&0&0&0\ 0&I&0&0\ 0&0&I&(I + R^c)}. $$ – Ben Grossmann Jul 19 '20 at 11:07
  • ...Where $R$ denotes a "right-shift" and $L$ denotes a "left-shift." – Ben Grossmann Jul 19 '20 at 12:05
  • 2
    As you implied in a comment, subject to the existence of an oracle that factorizes integers of the form $q^k-1$ for $k \le d$, there is a fast polynomial time algorithm for computing the order of a matrix in ${\rm GL}(d,q)$ using the minimal polynomial, and this is used in systems such as GAP and Magma. I was just trying it in Magma for $q=2$. For $d$ up to about 900 it is very fast indeed. After that, the factorization problem kicks in. Trying factorizations directly, it is having serious difficulties with $2^{929}-1$. – Derek Holt Jul 19 '20 at 12:56

1 Answers1

1

I could not find a proof or method how they obtained the order of the transformations

Note that the authors do not need a way to compute the order of a matrix $M$. Instead, since they are specifically looking for a matrix of size $n \in \{2^5,2^6,2^7\}$ of a prescribed form taken from finitely many possibilities, they need only have a way to check whether the order of such an $n \times n$ matrix is $n$.

With that in mind, suppose that $n = 2^k$ and we want to check whether the $n \times n$ matrix $M$ has order $n$. the following steps suffice:

  1. Compute $M^{n/2}$ (for instance, by $k-1$ steps of iterative squaring). If $M^{n/2} = I$, then $M$ does not have order $n$.

  2. Compute $M^{n} = (M^{n/2})^2$. If $M^{n} = I$, then $M$ has order $n$. Otherwise, $M$ does not have order $n$.

Note that this uses the fact that all proper divisors of $n = 2^k$ are divisors of $n/2 = 2^{k-1}$. The same does not hold true for $n = 96 = 3 \times 32$, so the above method would need to be modified for this case.

Ben Grossmann
  • 225,327
  • Thanks! The realization that I don't need to compute, but only to check is really important. – ambiso Jul 19 '20 at 14:02
  • Is the $n$ in "$n \times n$" and "order $n$" the same $n$? Because that's a deviation from what's required in the paper - $n \times n$ matrices of order $2^n - 1$. – ambiso Jul 19 '20 at 14:02
  • @cisnjxqu Yes, that's what I thought they were looking for; I guess I misread the paper then – Ben Grossmann Jul 19 '20 at 17:31