How to prove pairwise independence of a family of hash functions?

1.4k Views Asked by Bumbble Comm At 25 Mar 2026 - 7:09

I want to prove pairwise independence of a family of hash functions, but I don't know where to start.

Given the family of hash functions:

H with h(x) = a * x + b (mod M).

( Say h: U -> V, then: M is a prime and M >= IUI )

So how do I show that the family is pairwise independent. The definition is: The probability that h(u1) = v1 AND h(u2) = v2 is 1/M^2.

I can imagine that the solution has something to do with the modulo ring but I don't know how to get there.

Can someone help me?

Thanks a lot in advance!