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)

Get Unlimited 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  .

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.

 

Add to cart


Study Tools You Might Need

Not The Solution You Need? Search for Your Answer Here:

×

Login

Login or Sign up for access to all of our study tools and educational content!

Forgot password?
Register Now

×

Register

Sign up for access to all content on our site!

Or login if you already have an account

×

Reset password

If you have an active account we’ll send you an e-mail for password recovery

Or login if you have your password back