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