My question is the following:
Is there a polytime non-numerical algorithm for computing square root of perfect square integers?
The more elementary the algorithm is, the better!
EDIT: This is probably the most silly question I ever asked (I hope!). As pointed out by picakhu, since the input integer $n$ is perfect square, we can simply do a binary search to find the number whose square equals to $n$.
The following should suffice, from Cohen: A course in computational algebraic number theory.
