At modulus 1000003 the lab's prose produces no collision at all. That is a measurement of one choice, and the sweep beside it runs the same text and base at every prime under 200: 18 of the 46 collide, the largest of them 137, while 11 is clean. Collisions do not switch off above a threshold. What the analysis actually gives is an expectation over a randomly chosen modulus, which is a different statement from a promise about the one you picked.
Core ideas
The hard idea is which quantifier the analysis is over. The other two are the sweep and what a clean run does and does not license.
At modulus 1000003 the panel reports 41 windows, 4 candidates, 4 matches, 0 collisions and a verification bill of 12 characters — the smallest possible, since the four real occurrences must be checked. Nothing about that run is evidence that the modulus was large enough, because the same run at modulus 11, which is nearly five orders of magnitude smaller, is also clean on this text.
The lower table runs the identical text and base at every prime modulus from 2 to 199 and reports how many windows collide at each. Eighteen of the forty-six collide. The collide list is 2, 3, 5, 7, 13, 17, 23, 29, 37, 41, 47, 53, 67, 103, 109, 113, 131 and 137; the clean list begins 11, 19, 31, 43, 59. So 137 collides and 11 does not, on the same text, which is what it means for the answer to be a property of the text rather than of the size of the modulus.
What can be proved is that for a modulus drawn at random from a suitable range, the expected number of spurious hits is small — roughly n/q for a sufficiently large prime q. That is a statement about the average over choices. Fixing the modulus in the source code and then measuring one text converts it into no statement at all, and an adversary who knows the fixed modulus can build a text on which every window collides. Randomising the modulus is what makes the expectation available.
The material
The clean run, the sweep, why the collision set is not an interval, and what the expectation is an expectation over.
Keep the text the rain in spain stays mainly in the plain, the pattern ain and the base 256, and set the modulus to 1000003. The pattern now hashes to 383964, four windows hash to that value, all four are occurrences, and the panel's collision counter reads 0. The verification bill is 12 characters, which is 4 × 3 and cannot be lower.
That is the good case, and the page does not stop there. The lower table keeps this text and this base and replaces the modulus by every prime below 200 in turn.
There exist a text, a pattern and a base together with two primes q1 < q2 such that the hash collides at q2 and not at q1. So no threshold Q exists with the property that every modulus above Q is collision-free for a given input.
The table above exhibits one: with the text the rain in spain stays mainly in the plain, the pattern ain and base 256, the modulus 11 produces no spurious hit and the modulus 137 produces three.
A single instance settles the statement because the claim is existential. The reason is that a collision at modulus q means q divides the difference between two particular integers, and divisibility of a fixed number is not a monotone property of the divisor: 137 divides one of these differences and 11 divides none of them.
□
That proof shape is worth noticing because it is the opposite of the one this course usually needs. Here the measurement is the proof: the claim is that something exists, and a single exhibited pair establishes it. The claims that measurement cannot establish are the universal ones, and the next paragraph is about one of those.
Fix the text, the pattern and the base. A window collides at modulus q exactly when q divides the difference between that window's value and the pattern's. Each of those differences is a fixed integer below b^m, so it has at most m log b / log q prime divisors above q, and choosing q at random from a range of size R makes the chance that it divides any of the n differences at most a bound of the form n m log b / (R log R). That is the theorem, and its subject is the random choice.
Read what it does not say. It does not say that a particular large prime is safe on a particular text — 137 is not, here. It does not say the collision count falls as the modulus rises — the table shows 41 and 47 colliding while 43 does not. And it says nothing at all if the modulus is a constant in the source, because then there is no random choice to average over and an adversary can construct a text against it.
Each candidate costs m character comparisons to settle. At modulus 41 this text produces 7 candidates and a bill of 21 characters, of which 9 are wasted; at 1000003 it produces 4 and a bill of 12, with nothing wasted; at modulus 2 it produces 22 candidates, of which 18 are collisions. In the worst direction the verification dominates and the algorithm degenerates towards comparing every window in full, which is the naive matcher with extra arithmetic.
So the modulus is not a tuning detail. It decides how much of the algorithm's advertised advantage — constant work per window — survives contact with the input, and the only defensible way to choose it is at random from a large range, because that is the one choice the theorem covers.
Switch the preset to the binary one, where the alphabet is two characters and the base is 2, and the sweep reports 6 of the 46 primes colliding rather than 18. Switch to the repetitive abracadabra text at base 256 and it reports 15. The number is a property of the input triple and moves by a factor of three between presets, which is a third way of making the same point: it is not a constant of the method.
Interactive
Equal hashes are not a match, and the verification is not optional
Method
A clean run is one row of the table. Read the column it sits in before drawing anything from it.
0 collisions is the row. 18 of 46 is the column. A page that prints only the row has shown a measurement; the column is what says whether the row was luck.
Scan the clean list for a value smaller than something in the collide list. Here 11 is clean and 137 collides, which settles it: there is no size above which this input stops colliding.
Each candidate costs m. Going from 4 candidates to 22 takes the verification bill from 12 characters to 66 on a 43-character text, at which point the arithmetic saving has been spent.
The bound is an expectation over the modulus. A constant in the source code has no expectation attached and can be attacked; a modulus drawn at random from a large range is the object the proof is about.
The text is the rain in spain stays mainly in the plain, the pattern is ain, the base is 256. The pattern's unreduced value is 6383982 and every row below is that number and the window values reduced by a different modulus.
The middle block is the whole lesson in four numbers. Eleven is clean and a hundred and thirty-seven is not, so any sentence beginning “a modulus large enough to” has to be finished with something other than a size.
For a faded rehearsal, work out why modulus 2 is the worst. The supplied first move: at base 256 every character's contribution is even except when its code point is odd, so the hash modulo 2 is the parity of the last character's code point alone. Say how many of the 41 windows that puts in the candidate set, and then say what the verification bill becomes.
Then switch the preset to the binary text and read the sweep again. It reports 6 of 46 rather than 18. Before deciding that a small alphabet is safer, say what the base is in that preset and how many windows there are, and then say which of the three changes you would need to hold fixed to make the comparison mean anything.
You should be able to state what a collision at modulus q means arithmetically, exhibit a smaller clean modulus beside a larger colliding one, explain why that rules out a threshold, price candidates in character comparisons, and say why the modulus must be drawn at random for the expectation to apply.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.