factorization by finding modular square roots

Prove that having three distinct solutions of the conguence $\displaystyle x^2=y\mod n$, where $\displaystyle n,\,y$ are known and $\displaystyle n=pq$ is a product of distinct primes, we can find $\displaystyle p$ and $\displaystyle q$ efficiently.

I've managed to prove, with the Chinese remainder theorem, that the congruence always has four distinct solutions and that we can easily find the fourth solution when we have three.

Re: factorization by finding modular square roots

Quote:

Originally Posted by

**ymar** Prove that having three distinct solutions of the conguence $\displaystyle x^2=y\mod n$, where $\displaystyle n,\,y$ are known and $\displaystyle n=pq$ is a product of distinct primes, we can find $\displaystyle p$ and $\displaystyle q$ efficiently.

I've managed to prove, with the Chinese remainder theorem, that the congruence always has four distinct solutions and that we can easily find the fourth solution when we have three.

Suppose that the three solutions are r, s, t: $\displaystyle r^2\equiv s^2\equiv t^2\equiv y\pmod n.$ Then $\displaystyle 0\equiv r^2-s^2 = (r+s)(r-s)\pmod n.$ That can only happen if $\displaystyle s\equiv\pm r\pmod n$, **or** r+s and r–s are equal (mod n) to the two proper divisors of n, namely p and q. In the latter case, we have efficiently found p and q. So we have to deal with the former case, when $\displaystyle s\equiv -r\pmod n$ (we know that r and s are distinct, so we cannot have $\displaystyle s\equiv r\pmod n$).

In a similar way, $\displaystyle (r+t)(r-t)\equiv 0\pmod n.$ But t≠r and t≠–r(=s). Therefore r+t and r–t are equal (mod n) to p and q. So again we have efficiently found p and q.