Comment by arcastroe

Comment by arcastroe 4 days ago

6 replies

View on Hacker News

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.

dmurray 4 days ago

> It's not that each congruence gives you new information

So it's not that each congruence gives you N bits of information, and you want kN bits in total. It's more like each congruence has a 1/k chance of giving you the full kN bits.

But in some information theory sense those are the same! Or concretely, if you were testing a large quantity of numbers in parallel, you would get information from each congruence.

Reply View 3 replies
  • arcastroe 4 days ago

    I suppose you're correct. Even if you find a trivial congruence, you do get some information. Mainly: "It's not that one!" :)

    The same information as trying two bases that don't form a quadratic congruence at all

    Reply View 2 replies
    • thaumasiotes 3 days ago

      Well, if a+b and a-b are difficult to factor, finding more congruences might give you another pair x+y, x-y, and if that pair is nontrivial but also difficult to factor, you may be able to make progress by looking at x+y / a+b and x+y / a-b. As long as they're not integer multiples of each other, the combination of the two facts is more informative than either fact alone, in the sense that you're now trying to factor a smaller number.

      Reply View 1 reply
      • [removed] 2 days ago
        [deleted]
        Reply View 0 replies
phkahler 3 days ago

No, not that congruence. I mean a row in the big matrix. A residue r = x^2 mod m factored over the factor base. When you get enough of these you can derive a^2 - b^2 = 0 mod m. What does each factored r provide prior to having enough of them?

Reply View 0 replies