Is it easy (computationally) to take square roots of matrices over Z/nZ, if you know the factorization of n? More specifically, suppose I generate a random matrix M, and square it. Can a probabilistic polynomial time algorithm output M with reasonable probability?
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?
Edits:
Also at: https://math.stackexchange.com/questions/52474/taking-square-roots-of-matrices-over-z-nz
Clearly the problem is hard in the worst case, since the identity matrix has exponentially many square roots. So I guess the question is what to do in the average case.
