3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Do you know how to show that things have at most 2 square roots mod a prime? ​ ​ $\endgroup$
    – user991
    Mar 29, 2016 at 8:01
  • $\begingroup$ I was looking into that and found this: math.stackexchange.com/questions/633160/…. So, I do know the things listed there, but nothing much apart from that. $\endgroup$ Mar 29, 2016 at 8:23

1 Answer 1

7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.