factorization by finding modular square roots

Prove that having three distinct solutions of the conguence , where are known and is a product of distinct primes, we can find and 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

, where

are known and

is a product of distinct primes, we can find

and

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: Then That can only happen if , **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 (we know that r and s are distinct, so we cannot have ).

In a similar way, 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.