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

Problem Detail: 

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$?

Asked By : born

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9106