Suppose that the three solutions are r, s, t: Then That can only happen if ,orr+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.