Order of matrix in finite field GF(2) I was looking at George Marsaglia's paper Xorshift RNGs on xorshift random number generators where he states the following:

In order that a nonsingular n×n binary matrix T produce all possible
non-null 1×n binary vectors in the sequence β, βT, βT2 , . . . for
every non-null initial 1×n binary vector β, it is necessary and
sufficient that, in the group of nonsingular n×n binary matrices, the
order of T is 2n-1

Which appears to be equivalent to saying that, where k = 2n-1, Tk = I and for all j < k, Tj ≠ I. Equivalently, successive powers of T are periodic with period k.
Is there a way to determine what the order is of such a matrix, or even simply if the above condition is true, aside from checking if Tx = I for all factors x of k (not only prime)? If Tk = I and Tx ≠ I for all factors x<k, the above condition would be true (I think), but does there exist a less lengthy test that would work for large powers k such as 2160-1, or large numbers with a large number of factors?
 A: If you want to show that the order of a group element $T$ is $k$, you do not need to test all factors. It is enough to test for all prime factors $p\mid k$ that $T^{k/p}\neq I$ and that $T^{k}=I$. This can be done in polynomial time by iterated squaring (and some modifications of that), once you have the set of $p$. The hard part is getting the set of primes, currently no classical polynomial time algorithm is known for that for general $k$.
However you seem to be interested in a special $k=2^{160}-1$. This has some easy factors that can be computed by hand, e.g. $k=(2^{80}-1)(2^{80}+1)$, and computer algebra systems can factor such a "small number" as $k=2^{160}-1$ rather fast. So, using a computer algebra system built with these tricks verifying the order to be $k=2^{160}-1$ is doable. Here is a prime factorization of $k=2^{160}-1$:
$$
k=3\cdot 5^2\cdot 11\cdot 17\cdot 31\cdot 41\cdot 257\cdot 61681\cdot 65537\cdot 414721\cdot 4278255361\cdot 44479210368001
$$
Note: The quantum part of Shor's algorithm is a polynomial time quantum algorithm for order finding in groups. Currently that is of no practical relevance, as you will probably have not access to a sufficiently large quantum computer - as of 2022 noone has (officially).
