Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$ I'm trying to solve exercise 6.5 on page 309 from Richard Crandall's "Prime numbers - A computational perspective". It basically asks for an algorithm to factor integers in randomized polynomial time given an oracle for taking square roots modulo $n$.

I think, the basic idea is the following: Given a composite number $n$, to take a random element $r$ in $\left.\mathbb{Z}\middle/n\mathbb{Z}\right.$ and square it. If $r$ was a square, $r^2$ can have up to $4$ different square roots and the basic idea of the algorithm is that the oracle has some chance not to choose $\pm r$, but one of the other two roots. It will turn out that we then can determine a factor of $n$ using Euclidean's algorithm. 

I formalized this to

Input: $n=pq\in\mathbb{Z}$ with primes $p$ and $q$.

Output: $p$ or $q$


Take a random number $r$ between $1$ and $n-1$
If $r\mid n$ then return $r$ (we were lucky)
$s:= r^2\pmod{n}$
$t:=\sqrt{s}\pmod{n}$ (using the oracle)
If $t\equiv \pm r\pmod{n}$ then goto step 1.
Return $\gcd(t-r,n)$


One can show that $t \not\equiv \pm r\pmod{n}$ implies that $\gcd(t-r,n)\neq 1,n$ and therefore get that the return value of the algorithm is a non-trivial factor of $n$. 

Inspired by my main question "How do I prove that the running time is polynomial in the bit-size of the input?" I have some follow up questions:


Do I have to show that a lot of numbers between $1$ and $n-1$ are squares? There must be a well-known theorem or easy fact that shows this (well... not well-known to me ;-). 
Are there any more details I have consider? 
Has every square of a square exactly $4$ square roots modulo $n$?
Where in the analysis of the algorithm does the number of squares ("quadratic residues") come in? As to their number, you know that $a^2 \pmod{n}$ is always a square, and every number has up to $4$ square roots. That should help you show that there are a lot of squares.
Try to prove that your algorithm works, and see if anything is missing.
Suppose $n = pq$ ($p,q$ different primes) and $(x,n)=1$. Then if $x$ is a square, then $x$ has two square roots modulo $p$ and two square roots modulo $q$, and so four square roots in total by the Chinese remainder theorem. We know that a number $x$ such that $(x,p)=1$ has at most two square roots since the polynomial $t^2-x$ can have at most two roots modulo $p$. If it has one square root $y$ then $-y$ is another one.