# Quadratic residuosity problem reduction to integer factorization

How can one show how to reduce the quadratic residuosity problem to an integer factorization?

-

There exist efficient algorithms to compute quadratic roots modulo a prime or prime power.

If you know the factorization of the modulus you can use the above to compute quadratic roots mod the prime factors and then combine them using the chinese remainder theorem to efficiently compute the quadratic root of the full modulus.

Thus, if you can factor the modulus you can efficiently compute quadratic roots under that modulus.

-
So, solving the quadratic residuosity problem for a prime modulus is easy. It is hard when the mod is a composite number n = p x q. Finding the factors, solving the problem for independently for each factor p and q yields a solution to the problem mod n. Please correct me if I am wrong. – Faith Jul 21 '13 at 9:33
@Faith Correct. – orlp Jul 21 '13 at 11:04
How would Chinese reminder theorem will computer the quadratic root of the full modulus given the solutions of mod p and mod q? – Faith Jul 21 '13 at 20:35

The above discussion indicates how knowing the factors of n allows us to find the roots efficiently. If the modulus n has been factored into prime then its solution was discussed above.

However, the converse statement is also true, that is quadratic residuosity problem could reduce to integer factorization, meaning that an efficient solution of the quadratic problem could be used to solve the factorization of n= p x q efficiently. (i.e if the factorization of n is not known).

Say there were an efficient algorithm for finding square roots modulo a composite number. The congruence of squares discusses how finding two numbers x and y where x2 ≡ y2 (mod n) and x ≠ ±y suffices to factorize n efficiently.

then by following this steps

1. Generate a random number, square it modulo n, and have the efficient square root algorithm find a root.
2. Repeat until it returns a number not equal to the one we originally squared (or its negative modulo n),
3. Follow the algorithm described in congruence of squares. The efficiency of the factoring algorithm depends on the exact characteristics of the root-finder (e.g. does it return all roots? just the smallest one? a random one?), but it will be efficient.
-