# Quadratic Sieve: what's the next step after it fails?

Factoring some 20-45 digit values n with a (simple) quadratic sieve, the quadratic sieve may end up with pairs of x and y s.t. $x^2 \equiv y^2 \pmod n$, but neither x+y nor x-y has a nontrivial gcd with n for any of the pairs.
The contini pdf (www.crypto-world.com/documents/contini_siqs.pdf) is an excellent resource for this and related questions.

To factor these numbers, I've been trying a couple of things:

2) Add more tb-smooth squares' factorizations to the matrix in order to increase the dimension of the nullspace.

What is the best way to handle this?

explanation: For every Linearly Independent vector in the matrix's nullspace, there's a ½ chance of finding a good pair. If the nullspace has dimension around 10, that's a very high chance of success.

Update: Post above heavily edited to make it informative. Having too few vectors could potentially happen (e.g. if fewer than recommended smooth squares are found), but the problem I was having came from my own error.

-

In the QS algorithm, every linear combination adding up to a zero vector modulo $2$ has a chance of $1/2$ to give you a nontrivial factor.
Your suggestion 2) is the way to go, because adding additional numbers provides you with a lot more different linear combinations to get that zero-vector ($\phi(b)+1$ is just the minimal number required to find at least one set of linear dependent vectors).