Is it easy (computationally) to take square roots of matrices over Z/nZ, if you know the factorization of n?
If the matrix is diagonalizable, then does diagonalizing and taking the square roots work? What if the matrix isn't diagonalizable, or if the diagonal has entries which aren't squares? What does this imply about square roots of the matrix?
Sorry for not phrasing this question well originally. I am interested in finding ANY square root. But finding a random square root is even better. Also, you can imagine the input to be the square of a random matrix.