8
$\begingroup$

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

$\endgroup$

3 Answers 3

13
$\begingroup$
  • 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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Faith
    Jul 21, 2013 at 9:33
  • $\begingroup$ @Faith Correct. $\endgroup$
    – orlp
    Jul 21, 2013 at 11:04
  • $\begingroup$ How would Chinese reminder theorem will computer the quadratic root of the full modulus given the solutions of mod p and mod q? $\endgroup$
    – Faith
    Jul 21, 2013 at 20:35
4
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ This converse direction only applies to the problem of actually finding square-roots. Given just a boolean oracle (which says whether or not a given number is a quadratic resiude mod n), it does not appear to be known whether we can factor n. $\endgroup$ Apr 3, 2019 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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