9
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Legendre symbole of N mod p = 0. From my knowledge in NT, Zero is excluded from QR. $\endgroup$ – Robert NACIRI May 28 '16 at 20:32
  • $\begingroup$ @Robert NACIRI: I changed the notation to use $p_j$ rather than $p$, to clarify that I'm talking of primes in the factor base, not a factor of $N$. $\endgroup$ – fgrieu May 29 '16 at 9:07
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So why is it customary to restrict a factor base to QR in any serious implementation or article? $\endgroup$ – fgrieu May 27 '16 at 11:39
  • 1
    $\begingroup$ @fgrieu Right! But some strategies are more or less effective than others. Recall that the main objective is that $\prod Q(x_i)=v^2$ is QR, independantly of each $x_i$ in order to satisfy $\prod x_i^2-v^2=0$ [n] $\endgroup$ – Robert NACIRI May 27 '16 at 13:46
  • 3
    $\begingroup$ (As an aside, your link to Wolfram says Legendre symbol, not Jacobi symbol.) HAC 3.2.6 says "Thus the factor base need only contain those primes p for which the Legendre symbol (n/p) is 1", Doesn't that fully answer your question? $\endgroup$ – Mok-Kong Shen May 28 '16 at 7:32
  • 1
    $\begingroup$ @Mok-Kong Shen: your remark helped me fix a serious mistake in the question: I had written $\left({p\over N}\right)=+1$ which requires the Jacobi symbol, rather than $\left({N\over p}\right)=+1$ which is fine with just the Legendre symbol, and is a different filter. Also, your HAC reference helped find a partial answer. Thanks! $\endgroup$ – fgrieu May 28 '16 at 15:00
1
$\begingroup$

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.

$\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.