Let [m] denote the set {0,1,...,m − 1}. 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) H = {ha1,a2 : a1, a2 ∈ [m]}, where m is a fixed prime and
 
Notice that each of these functions has signature ha1,a2 : [m]2 → [m], that is, it maps a pair of integers in [m] to a single integer in [m].
(b) H is as before, except that now m = 2k is some fixed power of 2.
(c) H is the set of all functions f : [m] → [m − 1].

Transcribed Image Text:

haj.az (X1, X2) = a1x + a, X2 mod m. %3D haj.az (X1, X2) = a1x + a, X2 mod m. %3D