@gtbastos Here are some thoughts.
There are some rejection tests you can do, for example if N is a power of M then they will commute, so if they don't commute there is no solution. Probably inspecting the eigenvalues is the best way, but if they aren't in the field then there is extra work as @Carl Love pointed out - he has a nice post about that here: https://www.mapleprimes.com/questions/203977-How-To-Find-Roots-Of-Polynomial-In-Finite#answer215097
You can do it more easily if both M and N happen to have only one root in the field - then you can inspect all 5^9 powers of the eigenvalue of M to see which matches with the eigenvalue of N. If you can't factor at all, you can do the same thing with determinants - see attached - this takes only 15 seconds on my laptop. For determinants you may have to test more or revert to the full eigenvalue method. Is the maximum order of a matrix in the product group 5^9-1?
Both these methods can give false positives, so you then could test if the power you found actually works. A power of n or higher, where n is the matrix size, can be expressed as a linear combination of n-1 and lower powers, so that can be an efficient test (circumventing the discrete log problem to some extent). To test M^i, note the polynomial p_i(x) =q(x)p_M(x)+r(x), where p_i(x)=x^i, p_M(x) is the characteristic polynomial of M and q(x) and r(x) are the quotient and remainder when dividing x^i by p_M(x). If you take x=M in this polynomial, then p_M(M)=0 by Cayley-Hamilton, and M^i = r(M), so evaluate r(M) and see if it is N.