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.