Solution Found!
Let [m] denote the set {0, 1, . . . , m 1}. For each of the following families of hash
Chapter 1, Problem 1.29(choose chapter or problem)
Let denote the set For each of the following families of hash functions, say whether or not it is universal, and determine how many random bits are needed to choose a function from the family.
(a) , where m is a fixed prime and
Notice that each of these functions has signature that is, it maps a pair of integers in to a single integer in .
(b) H is as before, except that now is some fixed power of 2.
(c) H is the set of all functions .
Questions & Answers
QUESTION:
Let denote the set For each of the following families of hash functions, say whether or not it is universal, and determine how many random bits are needed to choose a function from the family.
(a) , where m is a fixed prime and
Notice that each of these functions has signature that is, it maps a pair of integers in to a single integer in .
(b) H is as before, except that now is some fixed power of 2.
(c) H is the set of all functions .
ANSWER:Step 1 of 5
a) , this is a family of hash functions and the value of is equal to . Family of this function is universal if it possesses the property of the probability of colliding x and y is equal to in this x and y are data terms, n is a prime number. Consider , for this hash function the probability such that or .
This can be also written as in the form of put and . Here m is a prime number , so unique inverse modulo for therefore and can be in the form of integer thus m possible values. Hence it hold the probability of and H is universal.