3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user1992284
    Commented Mar 19, 2014 at 23:26
  • $\begingroup$ 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. $\endgroup$
    – user1992284
    Commented Mar 20, 2014 at 2:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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