alt Hacker NewsOn a related note, I've often wondered what each congruence in the quadratic seive reveals. Once you have enough of them you can factor the number, but what does a partial set of congruences reveal?
Its a matrix problem, so each row could be reducing the degrees of freedom of something. But what? And in what space?
If:
a^2 = b^2 (mod m)
Then:
a^2 - b^2 = 0 (mod m)
(a + b)(a - b) = 0 (mod m)
So, (a + b) must be a multiple of one of the factors of m. And (a - b) must be a multiple of the other factor of m.
> I've often wondered what each congruence in the quadratic seive reveals.
Each congruence reveals that the sum of the bases (a plus b) contains a factor of m. And the difference of the bases (a minus b) contains another factor of m.
The only thing you have to watch out for is the trivial case when one of the factors you find through this method is "1" and the other factor is "m". That case isn't very helpful.
It's not that each congruence gives you new information. You only have to find one single non-trivial congruence. But the other (trivial) congruences you find along the way only reveal that 1*m=m, which you already knew.