# How would you prove a family of functions is universal?

A set of functions from a universe U of keys to n buckets is universal if for every pair of keys in U, say x and y, such that x != y, the probability of h(x) = h(y) is less than or equal to 1/n, for a random function h in the set of functions.

Say you're given a prime number p, and a random integer n, such that p is greater than or equal to n. Say we want to look at the family of functions where we pick a random integer i, and define each function hi = ((i * x) mod p) mod n. The input can be any integer from 0 to p-1, and the the output can be any integer from 0 to n - 1.

How would you prove that this family of functions is universal. Or similarly, if you pick an arbitrary p and n, how would you come up with a counter example?

To try to disprove it: look for a counterexample. When looking for a counterexample, I suggest starting with the smallest parameters you can, to make manual calculations tractable. In this case, you might start with prime $p=3$ and number $n=2$; I think that is the smallest possible parameter setting that meets your requirement. Now, calculate the probabilities explicitly and see if it meets the definition. (The numbers are so small you should be able to calculate that explicitly by just enumerating all cases.) What do you get?