Basics of Quadratic Sieve algorithm 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?

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