0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

A good approach is to simultaneously try to prove it, and try to disprove it.

To try to prove it: look at what the definition says, plug in the definition of the hash function, and see what number-theoretic fact needs to be true. Can you find any proof for this number-theoretic fact?

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?

If you try this, I think you'll be able to answer your own question. If you're still stuck, edit the question to show what you tried along each of these two directions and where you got stuck.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.