Quadratic residuosity problem reduction to integer factorization

Question

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

Answer 1

• Factoring $\longrightarrow$ square roots. Computing square roots modulo a prime $p$ is easy: if $p \equiv 3 \pmod 4$ and $a$ is a quadratic residue modulo $p$, then $a^{(p + 1)/4}$ is a square root of $a$ modulo $p$; for $p \equiv 1 \pmod 4$, you can use Cipolla or Tonelli–Shanks.

  Computing square roots modulo a composite of known prime factorization is easy: compute square roots modulo each factor separately and combine with the Chinese remainder theorem.

• Square roots $\longrightarrow$ factoring. It is well-known that an oracle $S$ for finding square roots of random elements of $\mathbb Z/n\mathbb Z$ can be used to make an efficient algorithm to factor $n$: pick $x$ at random, and if $y := S(x^2) \not\equiv \pm x \pmod n$, then $\operatorname{gcd}(x \pm y, n)$ is a nontrivial factor of $n$ since $y^2 \equiv x^2 \pmod n$ so $n \mid x^2 - y^2 = (x + y) (x - y)$, and by hypothesis neither $x + y$ nor $x - y$ is congruent to zero modulo $n$.

• Factoring $\longrightarrow$ quadratic residuosity. Deciding quadratic residuosity for a prime modulus $p$ is easy: just compute the Legendre symbol $(a|p) \equiv a^{(p - 1)/2} \pmod p$ and see whether it is 0 or 1.

  Deciding quadratic residuosity for a composite modulus of known prime factorization $n = pq$ is easy: $a$ is a quadratic residue modulo $n$ iff it is a quadratic residue modulo $p$ and a quadratic residue modulo $q$, which can be computed by the respective Legendre symbols.

• Quadratic residuosity $\stackrel?\longrightarrow$ factoring. We don't know!

  If you could find a way to factor $n$ using a decision oracle $D$ for deciding whether random elements of $\mathbb Z/n\mathbb Z$ are quadratic residues, you could publish it in a top-tier conference, because the state of the art to my knowledge is that such a reduction is known only in the generic ring model.

Answer 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.

Answer 3

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.