Basics of Quadratic Sieve algorithm

Question

I'm trying to understand Quadratic Sieve algorithm for integer factorization, I follow the description in the book "Prime Numbers" by Crandall and Pomerance, specifically the Algorithm 6.1.1. (Even though the question below apply to any description of QS, as far as I can see.)

Please, I have a few very basic questions about the method:

• in the initialization phase one finds the square roots ($a_i$) on the number being factored ($N$) modulo some prime ($p_i$). But in the description the roots are never mentioned again, what are they good for?

• sieve phase, this is possibly just me not understanding the text fully, that I should "sieve for $B$-smooth values". I think it is possible to read the "smooth" word that I have to try all the primes up to the bound, but I think what is meant here that I only should try the primes having Legendre symbol equal to one, from the previous phase. (I try both and there was no difference..?)

• why do I have to have $(K+1) \times K$ matrix in the linear algebra step ($K$ is the number of primes found during the initialization)? I mean, if I got lucky I could end up having just three exponent vectors summing to zero vector so I assume it is because the algorithm uses linear algebra method to find the right subset, correct?

• in the final step, what to do if the GCD does not reveal non-trivial factor? Simply compute more exponent vectors for the linear algebra step? Remove some of the already computed?

Answer 1

$(1)$ The purpose of the roots is to accelerate the search for numbers $x$ with the property that $\ \ x^2\mod N\ \ $ has small factors. The algorithm would also work for random numbers, but the quadratic residues are a significant improvement concerning speed.

$(2)$ A number is $B$-smooth , if it has no prime factor larger than $B$. The goal of the number field sieve is to find enough congruences $x^2\equiv y\mod N$ with $B$-smooth $y$

$(3)$ In fact, we could have a zero vector with less than $K$ rows, but the chance will not be very large , if the matrix is large. Moreover, we may need many congruences of the form $\ \ x^2\equiv y^2\mod N\ \ $. Theoretically, there is a chance of $\frac{1}{2}$ that such a congruence gives a non-trivial factor, but the congruences constructed are not random.

$(4)$ It is as you say. In fact, sometimes , no factor is found, some congruences are deleted and new congruences are calculated. I do not know however the details.

Answer 2

Regarding 1:

The problem is that you want to sieve for presence of prime factors in x * x mod N, with ceil(sqrt( N )) <= x < ceil(sqrt( 2 * N )) and hence x * x mod N = x * x - N, without actually computing the expensive x * x or x * x mod N. The a_i allow this.

The p in 2 < p <= B are searched so that [ a * a = N ] mod p contains 2 solutions a_1 and a_2. The number of solutions of [ a * a = N ] mod p can be zero, one or two. If there is one solution, then p | N, so this typically doesn't happen. The cases of zero and two solutions occur - apparently - with about equal probability.

The x's are sieved based on [ x = a_i ] mod p, hence augmenting s and t in x = a_1 + s * p and x = a_2 + t * p.

For such x, it holds that [ x * x mod N ] mod p = [ a_i * a_i + 2 * p * a_i + p * p - N ] mod p = [ a_i * a_i - N ] mod p = 0.

Conversely, any x can be written as x = q * p + r. What does [ x * x mod N ] mod p = 0 tell us about r?

It holds that 0 = [ x * x mod N ] mod p = [ x * x - N ] mod p = [ q * q * p * p + 2 * p * q * r + r * r - N ] mod p = [ r * r - N ] mod p.