Quadratic residue problem on composite integers

Question

Its believed that the quadratic residue modulo $n=p·q$ for large primes $p$ and $q$ is intractable, which forms the basis of some cryptosystems.

However, it is solvable if the factors of $n$ are know, such that the problem modulo a prime is easy (we use the Chinese reminder theorem) to simultaneously solve the problem for each prime factor.

The question is, is there any proof of why the same method for prime number should not work for composites?

Or, what if the same technique for the prime number case is applied to the composite number? What flaw might we see in the result?

Obviously the output won't be correct, is there a specific thing that can be said on the result? For example, let us say we wanted to solve the problem for some integer $i$ which we think is a prime (but without our knowledge, it is a composite), is there any thing in the result that can be detected, so that we know the integer in which we thought is prime happens to be not?

Answer 1

The computation of square roots modulo a composite $N$ is hard, because a method for computing square roots can be turned into a factoring method in the following way:

1. Choose an element $a$ modulo $N$ uniformely at random and compute $A=a^2 \pmod{N}$
2. Apply the square root computation technique on $A$, get result $a'$
3. If $a'=\pm a$ retry, else $gcd(a-a',N)$ is a non-trivial factor of $N$

An important argument here is that the square root computation cannot systematically return $a$ because it has no way to know which of the possible square roots of $A$ you started from (they are all equiprobable since you choose $a$ uniformly and kept it secret).

If you are asking about deciding whether an element is a square modulo $N$, the situation is a bit different. First, an element $a$ is not a square modulo $N$ if its Jacobi symbol of $a$ and $N$ is not $1$. But if the Jacobi symbol is $1$, the problem of deciding whether a number is a square is believed to be hard. However, for the decision problem contrary to the computational version, I am not aware of reduction to factoring.

Answer 2

The question appears to be: we have algorithms that determine where $a$ is a quadratic residue modulo a prime $p$; what happens if we run the same algorithm, but instead of giving it a prime $p$, we give it a composite number $N$?

Well, there actually two common algorithms used to determine whether a value is a quadratic residue modulo a prime, and they differ in what they do if you feed them a composite:

The first test is to compute $a^{(p-1)/2} \bmod p$; the result is 1 if $a$ is a quadratic residue, -1 if $a$ is a quadratic nonresidue (and 0 if $a=0 \bmod p$)

What happens if you feed it a composite number; that is $a^{(N-1)/2} \bmod N$? Well, it is far more likely that the result will be something other than 0, 1 or -1; that would prove that $N$ is not a prime.

This is a slightly tighter version of the Fermat primality test; it is indeed useful as a quick check. However, there are composite numbers that will fool it with high probability; if we are searching for a prime number, and it passes the Fermat test, we generally want to go on with other tests as well.

The other test I referred to is computing the Legendre symbol using the Law of Quadratic Reciprocity; this is a way to compute a value that is equal to $a^{(p-1)/2} \bmod p$; however it uses a different algorithm (and is often faster, depending on what your computing resources are).

However, if you feed in a composite number $N$ into the Legendre symbol logic, it no longer is the same value as $a^{(N-1)/2} \bmod N$; instead, it will always remain either 0, 1 or -1 (and so is not useful for determining whether $N$ is composite); instead, you've just computed what's known as the Jacobi symbol.

If the Jacobi symbol is 0, then $a$ and $N$ are not relatively prime. If the Jacobi symbol is -1, then $a$ is not a quadratic residue. However, if it is 1, it might be (and it might not be; determining any more information appears to be a hard problem)