Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$

Question

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$

1. Take a random number $r$ between $1$ and $n-1$
2. If $r\mid n$ then return $r$ (we were lucky)
3. $s:= r^2\pmod{n}$
4. $t:=\sqrt{s}\pmod{n}$ (using the oracle)
5. If $t\equiv \pm r\pmod{n}$ then goto step 1.
6. 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:

1. 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 ;-).
2. Are there any more details I have consider?
3. Has every square of a square exactly $4$ square roots modulo $n$?

Answer 1

1. 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.
2. Try to prove that your algorithm works, and see if anything is missing.
3. 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.

Answer 2

"2." Another detail to consider is that finding square roots modulo a large composite (your step 4) is proved to be as hard a factoring, and produces in any case a factorization of the large composite. See, for example, here for an application of their equivalent difficulty, and here for an explanation of how to factor the large composite if one can find square roots modulo the large composite.

So it would seem you have found the algorithm correctly! And since all the steps, like computing (t-r,n), and aside from the magical oracle, are proven polynomial it seems you have constructed a proof as well!