Digest collisions (the birthday bound)

How it behaves

One input on the horizontal axis, the others held fixed.

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

• 64 bits, 10⁹ rows → ≈ 2.7%
• 64 bits, 10¹⁰ rows → ≈ 93%
• 128 bits, 10¹⁰ rows → ratio ≈ 1.5 × 10⁻¹⁹

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

• Query Processing

  Why can one question be answered by plans whose costs differ by a factor of ten thousand, and what does each operator force the engine to do?

  $$1-\exp (-n^2/2^{b+1})$$

  Read it in place →