Suppose $N = pq$ is a product of two primes. Consider the following computational problem:
Prime decomposition problem (PD):
Given $N$ find $p$ and $q$.
Quadratic residuality problem (QR):
Given $N$ and arbitrary $x < N$ such that $GCD(x, N) = 1$ find $y$, such that $y^2 = x (\mod N)$ or output $-1$ if if it does not exist.
It is not hard to see, that QR can be reduced to PD in $O(\log^2 N)$ the following way:
How to solve QR using PD:
- Solve PD for $N$. Obtain $p$ and $q$
- Find $x_p < p$ and $x_q < q$ such that $x_p \equiv x (\mod p)$ and $x_q \equiv x (\mod q)$ (done in $O(\log N)$).
- Calculate $x_p^{\frac{p-1}{2}} (\mod p)$ and $x_p^{\frac{q-1}{2}} (\mod q)$ (done in $O(\log N)$). If any of this values turns out to be $-1$, then $x$ is non-residue.
- Use Tonelli–Shanks algorithm to find $y_p < p$ and $y_q < q$ such that $x_p \equiv y_p^2 (\mod p)$ and $x_q \equiv y_q^2 (\mod q)$ (done in $O(\log^2 N)$).
- Find $y$ by applying Chinese Remainder Theorem to $y_p$ and $y_q$ (done in $O(\log N)$).
My question is: can PD be polynomially (in respect to $\log N$) reduced to QR?
To be more exact: is there a way to factor $N$ that involves solving $O(\log^{k_1} N)$ instances of QR and performing $O(\log^{k_2} N)$ additional “easy” operations for some constants $k_1$ and $k_2$?