In the Quadratic Sieve, why restrict the factor base?

Question

In the Quadratic Sieve, when factoring a number $N$, many descriptions and most implementations select as the factor base the set of small primes $p_j$ less than some bound $B$ restricted to having Legendre symbol $\left({N\over p_j}\right)=+1$.

Why this restriction of the factor base to primes $p_j$ such that $N$ is a quadratic residue modulo $p_j$? I wonder, because:

• Wikipedia's introductory description of the Quadratic Sieve does not use such restriction, and works; the restriction is introduced in an example, without justification (in the article as it stands now).
• Such restriction considerably lowers the density of integers having all factors in the factor base, arguably making it harder to find $x$ such that $x^2\bmod N$ has all factors in the factor base (or more generally to find $(x,k)$ with $x^2-k\cdot N$ smooth).
• A find including a factor not matching the restriction can help a successful factorization; borrowing the example in Introduction to Mathematical Cryptography section 3.6, trying to factor $N=9788111$ (by sieving $x^2\bmod N$ for $x$ starting at $\lceil\sqrt N\rceil$, by the same algorithm as in Wikipedia), it is found 20 smooths values of $x^2\bmod N$ for $x>\sqrt N$ among which it is selected (by Gaussian elimination) $$\begin{align} 3129^2\bmod N&=2\cdot5\cdot11\cdot23\\ 3313^2\bmod N&=2\cdot7^2\cdot17\cdot23\cdot31\\ 3449^2\bmod N&=2\cdot5\cdot7^2\cdot11\cdot17\cdot23\\ 4426^2\bmod N&=2\cdot3\cdot47^2\\ 4651^2\bmod N&=3\cdot23\cdot31^3 \end{align}$$ where the last two relations would have been eliminated by the restriction of the factor base, since $\left({N\over 3}\right)=-1$; however, by taking the product of these relations, it is found that $$(3129\cdot3313\cdot3449\cdot4426\cdot4651)^2-(2^2\cdot3\cdot5\cdot7^2\cdot11\cdot17\cdot23^2\cdot31^2\cdot47)^2$$ is a multiple of $N$, from it is found $2741$, a nontrivial factor of $N$, by computing $$\gcd(N,3129\cdot3313\cdot3449\cdot4426\cdot4651-2^2\cdot3\cdot5\cdot7^2\cdot11\cdot17\cdot23^2\cdot31^2\cdot47)$$

Note: For the purpose of the question, please disregard the improvements of including $-1$ in the factor base; or/and allowing use of one or a few primes larger than the bound $B$; or/and (unless relevant) electing to factor $m\cdot N$ for a small multiplier $m$.

Answer 1

I believe Carl Pomerance (the inventor of the quadratic sieve algorithm) gives a great explanation in:

Pomerance, C. (2008). Smooth numbers and the quadratic sieve. In Algorithmic Number Theory Lattices, Number Fields, Curves and Cryptography (pp. 69-81). Cambridge: Cambridge University Press.

The quote below comes from page 72.

"A number $m$ is smooth if all of its prime factors are small. Specifically, we say $m$ is $B$-smooth if all of its prime factors are $\le B$. The first observation is that if a number in our sequence is not smooth, then it is unlikely it will be used in a subsequence with product a square. Indeed, if the number $m$ is divisible by the large prime $p$, then if $m$ is to be used in the square subsequence, then there necessarily must be at least one other term $m'$ in the subsequence which also is divisible by $p$. (This other term $m'$ may be $m$ itself, that is, perhaps $p^2 | m$.) But given that $p$ is large, multiples of $p$ will be few and far between, and finding this mate for $m$ will not be easy. So, say we agree to choose some cut off $B$, and discard any number from the sequence that is not $B$-smooth." [emphasis added]

This is in agreement with the answer given by @fgrieu.

Answer 2

Answering my own question, with some degree of uncertainty.

The basic Quadratic Sieve (as in Wikipedia's algorithm and the example quoted in the question) finds smooth integers among $x^2\bmod N$, for $x$ starting at $\lceil\sqrt N\rceil$. Until $x$ reaches $\lceil\sqrt{2N}\rceil$, it is searched smooth numbers among $x^2-N$. If this is divisible by a prime $p_j$, then $x^2\equiv N\bmod p_j$. Assuming $p_j$ is not a factor of $N$, it holds that $\left({N\over p_j}\right)=+1$. Thus the restriction of the factor base to such $p_j$ does not reduce the density of smooth integers within the integers sieved, as long as we are sieving integers of the form $x^2-N$.

In the last two relations out of six shown in the question, $x$ got so large that it is sieved values $x^2-2\cdot N$. If we used a factor base restricted to $p_j$ with $\left({N\over p_j}\right)=+1$, there would be very few finds. Hence, no such restriction is made. However, the algorithm has sieved more than $0.4\sqrt N$ values, and is thus very inefficient. In practice, if $N$ is large enough that QS is justified, and the factor base is reasonably chosen (large enough), $x$ will remain below $\lceil\sqrt{2N}\rceil$, only $x^2-N$ will be sieved, and the restriction can be made.

It seems that popular variants of the QS are looking for smooth only of the form $x^2-N$ with $x=a\cdot y+b$, for appropriately chosen $a$ and $b$; in particular, such that $a$ divides $(a\cdot y+b)^2-N$. That allows to restrict the factor base without lowering the performance of sieving. Restricting the factor base is good because it about halves the number of variables in the system of linear equations to be solved; and about halves the number of smooths to be found before a solution to such system can be found.

Answer 3

The condition $\genfrac(){}{}{a}{b}$=+1 doen't matter as the product of 2 QNR is a QR.In fact the idea of locking for numbers satisfying $x^2-y^2=k.n$ was firstly introduced by Gauss (1801) and was developped by Kraichick (1920) by searching for special sequences of the form $Q(x_i)=x_i^2 -n$ which factorize over small primes $\prod Q(x_i)=v^2$. In the exemple you gave the number of QNR are even, then in the product only QR factors are present. Selecting larger primes outside the factor base, need additional ressource in storage and computation and doen't give additionnal advantage in the form of Fermat difference.