 To prove that taking a random square root is as hard as factoring, we first note that in most cases there are four distinct square roots since "n" has two square roots modulo "p" and two square roots modulo "q", and each pair gives a square root modulo "n" by the chinese remainder theorem.Some of the four roots may have the same value, but only with extreme low probability.Now, if we can find two different square roots, "x","y" such that formula_19 but formula_20, then this immediately leads to a factorization of "n" since "n" divides formula_21 but it does not divide either factor.