Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
up vote 3 down vote accepted

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

share|improve this answer
I found the problem! A prime number snuck into my list of test numbers, leading me to believe the sieve was having problems that it wasn't. Sorry about that! From this post, I get the impression that the factorization step will always have a very high chance to succeed since 10,000 kernel vectors can be generated and tested in a few seconds. – user1992284 Mar 19 '14 at 23:26
except that those vectors need to be linearly independent for the ½ chance, so there's no reason to construct linear combinations of them. original post updated. – user1992284 Mar 20 '14 at 2:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.