Sieving the sequence $x^2-n$ to recognize b-smooth numbers

Question

I am currently programming the quadratic sieve and have several literature books / papers and will take an example out of [1] for my question:

[1] An Introduction to Mathemtaical Cryptography by J. Hoffstein, J. Pipher and H. Silverman.

[2] Prime Numbers by R. Crandall and C. Pomerance.

[3] Smooth numbers and the quadratic sieve by C. Pomerance.

To factorize a number $n$ with the quadratic sieve, we are looking for a product of numbers $x^2-n$ giving a perfect square. The numbers $x^2-n$ has to be B-smooth. We also only look prime numbers where the jacobi symbol is $(\frac{n}{p}) = 1$, so we can solve the equation $a^2 \equiv n\ \textrm{mod}\ p$ for every $p$ with $2 \leq p \leq B$. If $p = 2$ there is only one solution and for $p \gt 2$ there are either no solutions or two soluions. But in our case are always 2 solutions, because $n$ is a quadratic residue for our prime numbers.

I will now come to the point where my problem starts. In [1] and [3] is the sieve step explained to recognize B-smooth numbers in our sequence $x^2 - n$. We are looking for the numbers $x$ where $p\ |\ (x^2- n)$.

The values of $x$ can be found "easily" by the roots of $a^2 \equiv n\ \textrm{mod}\ p$ namely the number $x$ which are congruent to $a_1 \textrm{ mod } p$ or $a_2 \textrm{ mod } p$ ($a_1, a_2$ are the roots of $a^2$).

So, we start with the first number in our sequence $x^2-n$ where $x \equiv a_1 \textrm{ mod } p$ and then every $p$-th entry is divisible by $p$. We start again at some start point of $x^2 -n$ and look for a number $x$ for which $x \equiv a_2 \textrm{ mod } p$ hold.

Now I have tried to this with some example from the book but it will stop getting the correct entry of $x$:

In [1] is the example for the number $N = 9788111$. Also, the first 20 numbers which are 50-smooth are listed with the factorization of $x^2 - n$.

The first $x$ is $x = \Big\lceil\sqrt{N}\Big\rceil = 3129$.

It starts now with:

$3129^2 \equiv 2530 \textrm{ mod } 9788111$

$3130^2 \equiv 8789 \textrm{ mod } 9788111$

$3131^2 \equiv 15050 \textrm{ mod } 9788111$

...

$4394^2 \equiv 9519125 \textrm{ mod } 9788111$

Until this number everything works. My program gives the correct factorization. And if we test it with the prime number $p = 7$ and the roots $a_1 = 2$ and $a_2 = 5$, we see that $3131 \equiv 2 \textrm{ mod } 7$. So, we can divide $15050$ with $7$.

But the next number in the list, which is 50-smooth doesn't hold the procedure:

$4425^2 \equiv 4403 \textrm{ mod } 9788111$ and $4403 = 7 * 17 * 37$

We see, that $4403$ is divisible by $7$. That means that $4425$ has to be congruent to $2 \textrm{ mod } 7$ or $5 \textrm{ mod } 7$. But it's not. That means, that at some point I can't just count $x$ with $p$ to get the next number in the sequence which is divisible by $p$. I think its because that the result of $x^2 - n$ is bigger than $n$ self at some specifically $x$ like $4425$:

$4425^2 - n = 19580625 - 9788111 = 9792514 > 9788111$

So, my question is what is the reason that at some $x$ it doesn't work anymore? What can I do to restart the procedure with counting $x$ with $p$ to recognize the valid spot to divide with $p$.

Answer 1

The statement "To factorize a number $n$ with the quadratic sieve, we are looking for a product of numbers $x^2−n$ giving a perfect square" is incorrect is only a subset of a possible more general definition: looking for a product of numbers $x^2-k\cdot n$ giving a perfect square (by restricting the numbers to be suitably smooth, factoring them, and using some equivalent of Gaussian elimination to form the product so that the multiplicity of every prime in its factorization is even). Introducing $k$ allows more freedom in the search (but is seldom used in practice).

The definition of QS used in reference [1] is identical to that in Wikipedia. It is looking for smooths of the form $x^2\bmod n$. That falls under the more general definition of QS that I give, since $x^2\bmod n$ is $x^2-k\cdot n$ with $k=\Big\lfloor{x^2\over n}\Big\rfloor$.

The issue encountered in the question is that the sieving algorithm used finds $x$ such that $x^2-n$ is smooth; but when $x$ exceeds $\sqrt{2n}$, that sieving algorithm no longer is sieving $x^2\bmod n$.

Options to fix this

1. Sieve only $x^2-n$, including when that exceeds $n$; and use $x^2-n$ rather than $x^2\bmod n$ everywhere else. Problem is, the density of suitable $x$ decreases as $x$ grows. Also, that's not an option for large $n$, since sieving even a fraction of $(\sqrt2-1)\sqrt n$ values is way too long.
2. Sieve only $x^2-n$, but use a larger factor base. That increases the number of relations to be found, but increases the number of smooths retained even more, so that the required number of relations will be reached sooner.
3. Sieve $x^2-k\cdot n$ for several values of $k$. For example: until there is enough smooth collected, and for $k$ from $1$ onward, sieve $x^2-k\cdot n$ for smooths, varying $x$ from $\Big\lceil\sqrt{k\cdot n}\Big\rceil$ to $\Big\lfloor\sqrt{k\cdot n+m}\Big\rfloor$ for some bound $m$. That matches reference [1] when the bound $m$ is set to $n$. That could be viewed as an overly naive Multiple Polynomial Quadratic Sieve.
4. Sieve integers of the form $(a\cdot x+b)^2-n$, with $(a,b)$ chosen appropriately, in particular such that $(a\cdot x+b)^2-n$ is divisible by $a$ (allowing $a$ as a factor, if it does not belong to the factor base). This is what actually used variants of the Multiple Polynomial Quadratic Sieve do. The multiple polynomials allows to remain in the region where the un-factored part of what's sieved is small, so that the rate of finding smooth does not become vanishingly small. One advantage compared to the previous solution is that the factor base used for sieving is the same for all the polynomials used, see this question.

There are several other, independent optimizations of QS; including:

• Allow what's sieved to be negative, and include $p_0=-1$ in the factor base.
• Actually factor $m\cdot N$ for some small $m$ chosen to optimize the yield of the factor base.