3 ms·

I thought the comment was already too long, and was trying to give an outline and not dive into too many details. I've already omitted some of the methods to a

I thought the comment was already too long, and was trying to give an outline and not dive into too many details. I've already omitted some of the methods to assist with the factoring of small quadratic residues, for example, and this was another part where I thought I'd give the naive idea rather than too many explicit details. But you're absolutely right, and thank you for providing some of said details. It's nice to know that things I write are going to be checked by people who actually know more than I do.

cperciva 16y ago
If you had just stopped at "finding lineearly dependent rows of a sodding enormous matrix modulo 2" I wouldn't have said anything -- but mentioning elementary linear algebra was potentially misleading, so I figured it was worth adding the details there. :-) For what it's worth, there is actually some elementary linear algebra done before the heavy guns are brought out: If a prime only occurs in two or three relations, adding one of those relations to the other(s) will decrease n while increasing w by a small enough factor as to make the final Lanczos solve faster. (In rare cases it can be worth eliminating primes which occur in 4 relations or more, but usually not.)