fingerprinting

Comparing two enormous files byte by byte is slow, but comparing two short checksums is instant. If the checksums differ, the files certainly differ; if they match, the files are almost certainly the same. Fingerprinting is this trick made rigorous: replace each big object with a small random summary — its fingerprint — and compare fingerprints instead of the objects, accepting a tiny chance that two different objects collide to the same fingerprint.

Precisely: a fingerprint is a short hash of a large object, computed with a randomly chosen hash function so that distinct objects collide with only small probability. The standard scheme treats the object as a number and reduces it modulo a randomly chosen prime, or evaluates it as a polynomial at a random point. Two unequal objects x and y collide exactly when their difference is divisible by the random modulus; because a fixed nonzero difference has only a few prime divisors, a randomly chosen prime divides it with low probability, so Pr[fingerprint(x) = fingerprint(y) but x != y] is small. The textbook payoff is Rabin-Karp string matching: to find a length-m pattern inside a length-n text, fingerprint the pattern once, then slide a window across the text comparing the window's fingerprint to the pattern's. A rolling hash updates the window's fingerprint in O(1) as it shifts by one character (drop the leaving character's contribution, add the entering one), giving O(n + m) expected time instead of O(nm); on a fingerprint match you verify character-by-character to rule out the rare false positive.

Fingerprinting matters because it turns expensive equality tests on big data into cheap tests on small summaries, and it is the engine behind Rabin-Karp, Freivalds' check, content-addressed storage, and deduplication. It is the practical face of the idea that random summaries rarely coincide by accident. The honest caveat: fingerprints can collide, so a match is only probable equality — you either verify on a match (making it Las Vegas, always correct) or accept a controlled false-positive rate (leaving it Monte Carlo). And the collision guarantee depends on the modulus or evaluation point being chosen randomly; a fixed choice can be defeated by an adversary who constructs a collision.