# Find $k^{th}$ root of $M \in GL(n,F_2)$

Given $M \in GL(n,F_2)$ which is known to have a $k^{th}$ root. How can I find a root algorithmically? Can I find all roots?

Other than being invertible and having a $k^{th}$ root I know nothing of M.

If I'm lucky and it happens that $gcd(k, |GL(n,F_2)|)=1$ then I can find the root by raising $M$ to the appropriate power. I'm interested in solving it for the more general case.

(also, is there any software library that can do it for me?)

-
I'd start trying with k=2, and work from there. – Thomas Andrews Apr 10 '11 at 18:12

For any $n$ you can, in principle, find the roots algorithmically by brute force enumeration. When $n$ is small, say $n=2$ or $n=3$, this is actually a very feasible approach - after all, there are just 6 invertible $2\times 2$ matrices over $F_2$, and 168 $3 \times 3$ ones. Raise each one to the $k$th power and see what you get.
For larger $n$, you can probably start by conjugating $M$ into a more convenient form such as the Frobenius Normal form. This may or may not help but if it does it can save a lot of computation.
In principle. ${}$ – Mariano Suárez-Alvarez Apr 11 '11 at 5:02