Factoring large $N$ given oracle to find square roots modulo $N$

Question

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.

Answer 1

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:

1. For a fixed input, $S$ will always return the same square root.
2. 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:

1. Choose $x\in\mathbb Z_N^\ast$ at random.
2. Pass its square $x^2$ to $S$; call the result $y$.
3. If $x\equiv\pm y\pmod N$, we were unlucky: Start over with a new $x$.
4. 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$.