Section 3.9 due Oct. 15th

(Difficult) I understood how the square roots could give us a non-trivial factor of a composite number, but I could not understand how this was computationally equivalent to factoring the composite number. It seems that this would require comparing two numbers squared, mod n over and over. Rather than trying to divide by all primes less than the square root of n, we would have to compute the "square" of every number mod n then compare them with one another. In reality, no two integers less than the square root of n would have the same squared value, so we would only need to check those values greater than square root of n.