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$:
- select a random $s$ evenly distributed on $\{1\dots n-1\}$;
- compute $q=s^2\bmod n$;
- compute $r=\mathcal A(n,q)$; if algorithm $\mathcal A$ gives an indication of failure, loop at 1;
- compute $d=\gcd(n,r+s)$ and if $d=1$ or $d=n$, loop at 1;
- 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.
