How can one show how to reduce the quadratic residuosity problem to an integer factorization?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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