A result by Chowla/Fridlender/Salié says that (with a constant $c \gt 0$) there are infinitely many primes such that all integers $a$ with $1 \le a \le c \cdot \log(p)$ are quadratic residues mod $p$.
If $N$ is an odd composite integer of unknown factorization, we can look for a difference of squares representation of $N$ as
$$N = x^2 - y^2, x,y \in \mathbb{Z}. \tag 1$$
Let $p_1, p_2, \cdots, p_k$ be a prime basis where
$$M = \prod_{i=1}^k p_i \gt N \tag 2$$
and let
$$N \equiv N_i \equiv x_i^2 - y_i^2 \pmod {p_i}. \tag 3$$
Let $n_p$ denote the least quadratic non-residue modulo $p$.
Question: Is it possible to select $p_i$ such that $x_i^2 \bmod p_i, y_i^2 \bmod p_i \lt n_{p_i}$?
Context: If we are able to select $p_i$ such that $x_i^2 \bmod p_i,y_i^2 \bmod p_i \lt n_{p_i}$ then we can find $x_i^2, y_i^2$ modulo $M$ by applying Chinese Remainder Theorem in time
$$ \begin{align} O(c_1 \log p_1 & \cdot c_2 \log p_2 \cdots c_{k-1} \log p_{k-1} \cdot c_k \log p_k) \\ & \approx O(C \log p_k \cdot \log p_k \cdots \log p_k) \\ & \approx O(C (\log p_k)^k) \\ \end{align} \tag 4 $$
The implication of an affirmative answer means there is a polylogarithmic time algorithm for integer factoring.
Claim: We can effectively select $\{p_i\}$ such that $M \gt N \land x_i^2 \bmod p_i, y_i^2 \bmod p_i \lt n_{p_i}$.
Can we prove or disprove this claim?
Note: Some empirical testing shows that the primes in the basis have to be $\ge 5$. This was established by running brute force Chinese Remaindering and determining that for some $M_i = \prod_{j = 1}^i p_j$ the set of Chinese Remainder solutions is empty. This condition does not arise when the smallest prime in the basis is $5$.