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

Question

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:

• finding the order of a matrix in GL(3,Z)

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:

• Computing the order of a group element
• Orders of Elements in GL(2,R)

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!

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