# Compute the order of an element in $GL(n, 2)$

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.

• 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
• 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
• 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
• 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

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.

• Thanks! The realization that I don't need to compute, but only to check is really important. – cisnjxqu 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$. – cisnjxqu 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