Order of matrix in finite field GF(2)

Question

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, βT² , . . . 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 2ⁿ-1

Which appears to be equivalent to saying that, where k = 2ⁿ-1, T^k = I and for all j < k, T^j ≠ 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 T^x = I for all factors x of k (not only prime)? If T^k = I and T^x ≠ 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 2¹⁶⁰-1, or large numbers with a large number of factors?

Answer 1

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