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?
How would you prove a family of functions is universal?
proof techniques;probability theory;hash;hashing