3
$\begingroup$

I am unable to prove the following theorem:

If for a $1/(\log(n))$ fraction of the quadratic residues $q\pmod n$ one could find a square root of $q$, then one could factor $n$ in random polynomial time. $n$ is the product of two large distinct primes.

$\endgroup$
1
$\begingroup$

Let $\mathcal A$ be the hypothetical algorithm in the question, with input $(n,q)$, output $r$, such that $r^2\equiv q\pmod n$ for a $1/(\log(n))$ fraction of the quadratic residues $q\pmod n$, running in random polynomial time w.r.t. $\log(n)$, restricting to $n$ product of two large distinct primes.

Let $\mathcal F$ be the following algorithm with input $n$ restricted as above, and output $d$:

  1. select a random $s$ evenly distributed on $\{1\dots n-1\}$;
  2. compute $q=s^2\bmod n$;
  3. compute $r=\mathcal A(n,q)$; if algorithm $\mathcal A$ gives an indication of failure, loop at 1;
  4. compute $d=\gcd(n,r+s)$ and if $d=1$ or $d=n$, loop at 1;
  5. output $d$.

This factors $n$ because

  • Given that factors of $n$ are large, the proportion of $q$ that share a factor with $n$ is so low that they can't constitute a significant share of the $1/(\log(n))$ success rate of algorithm $\mathcal A$ over the whole set of $q$, thus the success rate of $\mathcal A$ is near $1/(\log(n))$ including for other $q$.
  • When step 2 of algorithm $\mathcal F$ invokes $\mathcal A$ with $q$ coprime with $n$ (that is on iterations with $s$ coprime with $n$, which are the vast majority), $q$ is evenly distributed over these other $q$, hence $\mathcal A$ will succeed with odds next to $1/(\log(n))$.
  • When $\mathcal A$ succeeds with $q$ coprime with $n$, and since $n$ has two factors, there are four square roots of $q$; since $s$ is random and was not an input of $\mathcal A$, which root $r$ was output by $\mathcal A$ is independent of which root $s$ is. For two out of these four possible $s$, thus with odds $1/2$, step 4 will compute a $d$ that is a nontrivial factor of $n$.

This proves that for $n$ as restricted of unknown factorization, inverting $r\to q=r^2\bmod n$ for random $r$ (or random $q$) is of hardness comparable to factorization of $n$.


Detailed proof with explicit bound on how large the factors of $n$ need be:

  • Let $p_1$ and $p_2$ be the two large (thus odd) distinct primes with $n=p_1p_2$. The $n-1$ possible values of $s$ can be split into two categories, which together form the whole set of quadratic residues $q$:
    • $p_1+p_2-1$ values with $\gcd(n,s)\ne1$, which generate $(p_1+p_2-2)/2$ quadratic residues $q$ with $\gcd(n,q)=1$,
    • $(p_1-1)(p_2-1)$ values with $\gcd(n,s)\ne1$, which generate $(p_1-1)(p_2-1)/4$ quadratic residues $q$ with $\gcd(n,q)\ne1$.
  • That gives us a total of $(p_1+1)(p_2+1)/4-1$ quadratic residues $q$. Algorithm $\mathcal A$ succeeds for at least an $1/(\log(n))$ fraction of this total, among which at least $((p_1+1)(p_2+1)/4-1)/\log n-(p_1+p_2-2)/2$ values of $q$ in the second category.
  • We can assume $\min(p_1,p_2)>4\log(n)$ (noticing that otherwise trial division would factor $n$ in polynomial time w.r.t. $\log(n)$ anyway). With that bound and even distribution of $s$, $\gcd(n,q)\ne1$ and $q$ is among those for which $\mathcal A$ succeeds for at least an $1/(2\log(n))$ fraction of $s$.
  • When this happens, we have $r^2\equiv q\equiv s^2\pmod n$, thus $(r-s)(r+s)\equiv0\pmod n$, thus $(r-s)(r+s)\equiv0\pmod{p_1}$ and $(r-s)(r+s)\equiv0\pmod{p_2}$, thus $r-s\equiv0\pmod{p_1}$ or $r+s\equiv0\pmod{p_1}$, and $r-s\equiv0\pmod{p_2}$ or $r+s\equiv0\pmod{p_2}$.
  • When this happens, $\mathcal A$ has worked without knowing $s$ randomly chosen at step 1; hence each of the four $s$ possible for the $q$ handed to $\mathcal A$ is equally likely, and with odds $1/4$ we have $r+s\equiv0\pmod{p_1}$ and $r+s\not\equiv0\pmod{p_2}$, thus $d=p_1$ at step 4; and with odds $1/4$ we have $r+s\not\equiv0\pmod{p_1}$ and $r+s\equiv0\pmod{p_2}$, thus $d=p_2$ at step 4.
  • It follows that algorithm $\mathcal F$ is expected to reach the final step 5 after no more than $\mathcal O(4\log(n))$ iterations, with each step of each iteration running in random polynomial time w.r.t. $\log(n)$; so the whole algorithm does, and outputs a factor of $n$, Q.E.D.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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