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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.