Factoring large $N$ given oracle to find square roots modulo $N$ When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $\mathbb Z_N^\ast$ have either
  zero or four square roots. A quarter of the points have four square roots; the rest have no square
  root. The four square roots of $x\in\mathbb Z_N^\ast$ will look like $\pm a$, $\pm b$. (Of course, $-a$ means $N-a$ since
  we’re working modulo $N$.) Suppose that I give you an efficient deterministic algorithm $S$ that, on
  input $x$ that has square roots, finds some square root of $x$. (If $x$ does not have a square root, it returns
  $\bot$.)
  
  Use $S$ to make an efficient probabilistic algorithm $F$ that factors $N$. [Hint: If you can find two
  square roots of a number, call them $a$ and $b$, which are not of the form $a \equiv \pm b \pmod N$, then you
  can factor $N$. Show how.] Note: You only get to call $S$ as a black-box, so you don’t know a priori
  which of the square roots it will find.


I am having trouble understanding this homework question, could someone please guide me or give a hint on how to proceed? What I have come up with till now is,
first call algorithm $S$ on some number to find a square root $a$. Call it repeatedly until I get $b$ which is not of the form $a \equiv \pm b \pmod N$. Repeat this for all points.
I am still stuck on how I use this to factor $N$ though.
What I have come up with till now is, first call algorithm $S$ on some number to find a square root $a$. Call it repeatedly until I get $b$ which is not of the form $a\equiv\pm b\pmod N$. Repeat this for all points.


This has (at least) two problems:


For a fixed input, $S$ will always return the same square root.
You can not "repeat this for all points" since there are $\mathcal O(N)$ of them, hence your algorithm $F$ will not be (probabilistic) polynomial-time.




As to how we can fix this: Since $S$ will only give us one square root, we somehow have to obtain the other one (modulo negation) ourselves. A good (efficient) way to do this is to simply construct the number given to $S$ in a way that we already know one of its square roots, and hope that $S$ will give us the other one. Here's an algorithm:


Choose $x\in\mathbb Z_N^\ast$ at random.
Pass its square $x^2$ to $S$; call the result $y$.
If $x\equiv\pm y\pmod N$, we were unlucky: Start over with a new $x$.
At this point, we know from
$$ x^2\equiv y^2\pmod N $$
that
$$ x^2-y^2=(x+y)(x-y) $$
is a non-zero multiple of $N$ while neither $x+y$ nor $x-y$ alone is, hence we can recover a factor of $N$ by computing
$$ \gcd(x+y,N) \text. $$


Now we would like to prove that this algorithm is (probabilistically) efficient. Our choice of $x$ is equivalent to first choosing some square $r$ at random and then choosing $x$ as one of $r$'s square roots also at random. The oracle $S$ is deterministic, hence will always return the same square root $y$ of $r$. Therefore we have a probability of $\frac12$ that our choice of $x$ is not in the same "class" as $y$, i.e. $x\not\equiv\pm y\pmod N$, thus yielding a factorization. Clearly one iteration of this algorithm runs in polynomial time, and the expected number of iterations to succeed is only $1+\frac12+\frac14+\dots=2$. Therefore $F$ efficiently factors $N$.