Let [m] denote the set {0,1,...,m - 1). For each of the following families of hash functions,
Fantastic news! We've Found the answer you've been seeking!
Question:
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 = (hal ,a2 : al, a2 ∈ [m]}, where m is a fixed prime and
h a1, a2 (x 1 , x 2 ) = a 1 x 1 + a 2 x 2 mod m.
Note: Each of these functions has signature h al , a 2 : [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].
Related Book For
Finite Mathematics and Its Applications
ISBN: 978-0134768632
12th edition
Authors: Larry J. Goldstein, David I. Schneider, Martha J. Siegel, Steven Hair
Posted Date: