Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers 2

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.

share|improve this answer
    
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. –  nightcracker 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
add comment

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.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.