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

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