1
$\begingroup$

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!

$\endgroup$
6
  • 2
    $\begingroup$ 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). $\endgroup$ – Ben Grossmann Jul 19 '20 at 10:13
  • 2
    $\begingroup$ 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$. $\endgroup$ – Ben Grossmann Jul 19 '20 at 10:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Ben Grossmann Jul 19 '20 at 10:41
  • $\begingroup$ 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)}. $$ $\endgroup$ – Ben Grossmann Jul 19 '20 at 11:07
  • 2
    $\begingroup$ 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$. $\endgroup$ – Derek Holt Jul 19 '20 at 12:56
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks! The realization that I don't need to compute, but only to check is really important. $\endgroup$ – cisnjxqu Jul 19 '20 at 14:02
  • $\begingroup$ 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$. $\endgroup$ – cisnjxqu Jul 19 '20 at 14:02
  • $\begingroup$ @cisnjxqu Yes, that's what I thought they were looking for; I guess I misread the paper then $\endgroup$ – Ben Grossmann Jul 19 '20 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.