When a fingerprinting service must undo multiplications modulo n, how does a prime modulus differ from a power-of-two one?

## What the modulus actually decides A rolling fingerprint treats a window of bytes as the coefficients of a polynomial in some base `b`, evaluated modulo `n`. Advancing or normalising a window means undoing a multiplication by `b`, which requires an **inverse of `b` modulo `n`** - and an inverse exists exactly when `gcd(b, n) = 1`. Choosing `n` therefore chooses which bases are legal and how strong a statement can be made about collisions. It is the kind of decision that is cheap on the whiteboard and expensive later, because stored fingerprints are meaningless the moment the modulus changes. ## A power-of-two modulus With `n = 2^k`, the only prime factor in play is 2. So: - **The invertible residues are exactly the odd ones** - half of all residues. Any even base is permanently un-undoable. - **Reduction is a mask**, the cheapest reduction there is, and products wrap naturally in fixed-width arithmetic. - **The low bits are structurally weak.** For an odd base `b`, every power `b^i` is odd, so modulo 2 the whole fingerprint reduces to the sum of the window's bytes modulo 2. **The lowest bit of the fingerprint is a parity check** over the window - one whole bit of output that an adversary, or merely an unlucky data distribution, can predict without touching the rest. - **No useful root bound exists.** The argument that limits collisions needs every nonzero residue to be invertible, and modulo `2^k` most are not. ## A prime modulus With `n = p` prime, arithmetic modulo `p` is a field: **every nonzero residue has an inverse**. That single property buys the guarantee: 1. Two distinct windows of length `L` give two different coefficient vectors, so their difference is a **nonzero** polynomial of degree at most `L-1`. 2. Over a field, a nonzero polynomial of degree `d` has **at most `d` roots**. 3. A collision means the base `b` is a root of that difference, so at most `L-1` of the `p-1` nonzero base choices collide - and a base drawn uniformly at random collides with probability at most `(L-1)/(p-1)`. That is a bound, not an impossibility: collisions still happen, and a system that must be certain still verifies a match directly. What the prime modulus buys is a **number** to reason about, tunable by making `p` larger. ## Side by side | | modulus `2^k` | prime modulus `p` | |---|---|---| | invertible residues | the odd ones, half of them | every nonzero one | | legal bases for rolling | odd bases only | any nonzero base | | reduction cost | a mask | a division-like step | | structure in the output | low bit is a parity of the window | no comparable structure | | collision statement | none of this form | at most `L-1` of `p-1` bases | ## Making the call The questions worth asking before picking, roughly in order: - **Does anything adversarial reach this input?** If the data can be shaped by whoever is being fingerprinted, the predictable low bits of a power-of-two modulus are an invitation, and the provable bound is worth the slower reduction. - **Is the base fixed or chosen at run time?** A fixed, audited odd base survives a power-of-two modulus. A base drawn at start-up, or derived from configuration, is far safer against a modulus where every nonzero choice is legal. - **How long do fingerprints live?** A value compared within one request is a different risk from one persisted and compared months later. Persistence turns the modulus into a format decision: version it, because changing it invalidates every stored value at once. - **Where is the real cost?** Reduction is usually not the bottleneck next to reading the data being fingerprinted. Paying a measurable cost for an unmeasurable property is a bad trade; paying an unmeasurable cost for a provable bound is usually a good one. ## The failure this prevents The characteristic incident is not a crash. It is a comparison layer that silently reports more matches than it should - because the base shares a factor with the modulus and the shift was never truly undone, or because the low bits carry almost no information and near-misses land on the same value. Both are choices about the modulus made months earlier by someone who was thinking about reduction cost.