Show that if you can find four solutions b of $b^2\equiv a\pmod n$, where $n=p*q$, then you can find $p$, $q$

43 Views Asked by At

Given is that $n=p*q$ for different odd primes $p,q$ and you know $n$, but do not know $p, q$. Let $a$ be a quadratic residue ($mod$ $n$). I need to show that if you have a way to find the four solutions b of $b^2\equiv a\pmod n$, then you can compute $p$ and $q$.

I started with writing down $b_1^2$$=n*k+a$ and this is the same as $b_1^2$$=p*q*k+a$, and therefore $p=(b_1^2-a)/(q*j)$. And for the other solutions of b, this also holds, so I also have $p=(b_2^2-a)/(q*k)$, $p=(b_3^2-a)/(q*l)$ and $p=(b_4^2-a)/(q*m)$. But how do I show that you know $p$ and $q$?

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose we have $b_1^2=n\cdot k_1+a$ and $b_2^2=n\cdot k_2+a$. Let's take a look at $b_1^2-b_2^2=(b_1-b_2)(b_1+b_2)=n(k_1-k_2)=p\cdot q\cdot(k_1-k_2)$. Now, one of the numbers $b_1-b_2$ and $b_1+b_2$ must be divisible by $p$. Also, one of these numbers must be divisible by $q$. Can it be the same number? Well, it can't be $b_1-b_2$, because $0\le b_i<n$ (a condition which you did not mention explicitly, but without which the whole problem doesn't make any sense), so $b_1-b_2<n$, so it can't be divisible by $n$, which means it can't be divisible by $p$ and $q$ simultaneously. Now what about $b_1+b_2$? Chances are it will be divisible by $n$, if $b_2=n-b_1$. In this case just throw away $b_2$ and take instead $b_3$ (supposedly different from $b_2$, of course), for which this would not be the case.

OK, so finally we have two numbers one of which is divisible by $p$ and another by $q$. Now let's simply find the GCDs of $n$ and each of these numbers, and that would be our $p$ and $q$.