3
$\begingroup$

Is it easy (computationally) to take square roots of matrices over $\mathbb{Z}/n\mathbb{Z}$, 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.

  • 1
    @Jeff: I would expect diagonalization algorithms that work over finite fields would be a good way to go, though you may run into trouble when working over $\mathbb{Z}/n\mathbb{Z}$; as to what to do in the other cases, I don't know off-hand.2011-07-20

1 Answers 1