This is a follow up to using 8x8 binary matrices as a hash. Partially quoted for convenience:
I had the idea of computing a 64 bit hash of a text string by assigning a unique binary 8x8 matrix to each character, and computing the hashes of larger strings by multiplying the matrices corresponding to the substrings. In this system both addition and multiplication of matrix elements would be modulo 2.
I successfully implemented this scheme but immediately noticed some problems with choosing my 256 seed matrices (one for each 8-bit character). In particular, when matrices are chosen at random and non-invertible matrices are filtered out, it appears to be very likely that the matrix when cubed will equal its own inverse, causing it to become identity when raised to the 6th power. I can filter out these matrices when choosing my seeds, but I would prefer something more robust. To that end, a few questions:
1) Is there a way to test that an invertible binary matrix is 'prime', i.e. not a product of any two binary matrices other than itself and identity?
2) Is there a way to test that a binary matrix, when raised to successive powers, will visit the largest possible set of matrices before repeating?
3) Are questions 1 and 2 the same question?
For question 1).
Since $GL_8(F_2)$ is a finite group with $\alpha=\Pi_{k=0}^7(256-2^k)=5348063769211699200=127\times 17\times 2^{28}\times 3^5\times 5^2\times 7^2\times 31$ elements, for every $A\in GL_8\setminus I_8$, there is $0<k\leq \alpha$ s.t. $A^k=I_8$. Consequently, there are no prime invertible matrices ($B=A^i(A^{k-i}B)$).
For question 2).
In fact, (if $A$ is invertible), $k$ is a divisor of $\alpha$, that is $k=127^u\times 17^v\times 2^w\times 3^x\times 5^y\times 7^z\times 31^r$, where $u\leq 1,v\leq 1,w\leq 28,x\leq 5,y\leq 2,z\leq 2,r\leq 1$.
EDIT 1. Finally, if we want the order of $A$, then we start with the expoent $\alpha$ and simply fall gradually the exponents of $127,17,2,3,5,7,31$. We test at most $1+1+28+5+2+2+1=40$ powers of $A$.
EDIT 2. When I randomly choose $10$ invertible $A$, I find the following associated orders: $255,93,42,126,127,42,84,15,127,93$. I do not see how you can find mostly matrices $A$ s.t. $A^6=I_8$...
Of course, matrices $A$ can be generated until obtaining a matrix that has a large order. Yet, such a matrix can be very special, that is not suitable for a cryptographic system.
EDIT 3. After testing $50000$ invertible matrices, I find $255=2^8-1$ as maximum order; these matrices constitute $\approx 6.1\%$ of invertible matrices.
In fact, this result is known: cf. the Ilya Bogdanov's answer in https://mathoverflow.net/questions/109483/maximal-order-of-elements-in-gln-p