2. Recall Zp, the integers mod p where p is a prime, and let Z*, denote the numbers Z, excluding 0. Let Bpm be the family of hash functions defined { ha for some a E Z*p, such that ha(x) = (( ax mod p) mod m)}. (This is not Upm because the hash functions don't include a b component.) Assume p and m are both prime, and p >>m. (a) How many functions are there in Bpm? (b) Argue that for each a E Z*each function ha is a one-to-one correspondence between the members of Zp and the set la = kufor some x in Zp, h(x) = u}. What are the sizes of Ia and Z*p? (c) Show that, for any x, y in Zp, if x # y, ( ax mod p) # ( ay mod p) (d) For all x,y, calculate the number of values of a in Zp for which ha(x)= ha(y) (i.e. for how many values of a is (ax mod p) =m ( ay mod p)? (Fact from number theory: For all z = 0, for all i: Pr{ (az mod p) =i} = 1/p, where probability is taken over all a EZ*p) (e) Prove that Bpm is a nearly-universal family of hash functions, i.e. for all x,y E Zp where xty, Prob {ha(x) = haly)} = 2/m where the probability is taken over the functions in Bpm. Background about Zp: If p is a prime, then Zp is the field of integers mod p. (Another example of a field is R the set of rational numbers.) In a field, the usual properties of numbers hold (as they do in R), e.g.: Zp is closed under +mod p and Xmod p and these operations are associative and commutative All numbers have additive inverses (such that a number plus its inverse sums to 0) and subtraction of x is defined as addition of x's additive inverse. All numbers but I have multiplicative inverses (such that a number times its inverse is 1) and division by a number is defined as multiplication by its inverse. Xmod p distributes over +mod p (i.e. for all a, b, c, a(b+c) =m ab +ac ). For any two numbers u and v in Zp, uv=0 iff u=0 or v=0 2. Recall Zp, the integers mod p where p is a prime, and let Z*, denote the numbers Z, excluding 0. Let Bpm be the family of hash functions defined { ha for some a E Z*p, such that ha(x) = (( ax mod p) mod m)}. (This is not Upm because the hash functions don't include a b component.) Assume p and m are both prime, and p >>m. (a) How many functions are there in Bpm? (b) Argue that for each a E Z*each function ha is a one-to-one correspondence between the members of Zp and the set la = kufor some x in Zp, h(x) = u}. What are the sizes of Ia and Z*p? (c) Show that, for any x, y in Zp, if x # y, ( ax mod p) # ( ay mod p) (d) For all x,y, calculate the number of values of a in Zp for which ha(x)= ha(y) (i.e. for how many values of a is (ax mod p) =m ( ay mod p)? (Fact from number theory: For all z = 0, for all i: Pr{ (az mod p) =i} = 1/p, where probability is taken over all a EZ*p) (e) Prove that Bpm is a nearly-universal family of hash functions, i.e. for all x,y E Zp where xty, Prob {ha(x) = haly)} = 2/m where the probability is taken over the functions in Bpm. Background about Zp: If p is a prime, then Zp is the field of integers mod p. (Another example of a field is R the set of rational numbers.) In a field, the usual properties of numbers hold (as they do in R), e.g.: Zp is closed under +mod p and Xmod p and these operations are associative and commutative All numbers have additive inverses (such that a number plus its inverse sums to 0) and subtraction of x is defined as addition of x's additive inverse. All numbers but I have multiplicative inverses (such that a number times its inverse is 1) and division by a number is defined as multiplication by its inverse. Xmod p distributes over +mod p (i.e. for all a, b, c, a(b+c) =m ab +ac ). For any two numbers u and v in Zp, uv=0 iff u=0 or v=0