# Exercise 11.3.6

$\star$ Let $U$ be the set of $n$-tuples of values drawn from $\mathbb{Z}_p$, and let $B = \mathbb{Z}_p$, where $p$ is prime. Define the hash function $h_b : U \rightarrow B$ for $b \in \mathbb{Z}_p$ on an input $n$-tuple $\langle a_0, a_1, \ldots , a_{n-1} \rangle$ from $U$ as

$$h_b( \langle a_0, a_1, \ldots, a_{n-1} \rangle ) = \left( \sum_{j=0}^{n-1}{a_j b^j} \right) \bmod p$$

and let $\mathscr{H} = \left\{ h_b : b \in \mathbb{Z}_p \right\}$. Argue that $\mathscr{H}$ is $((n - 1)/p)$-universal according to the definition of $\epsilon$-universal in Exercise 11.3-5. (Hint: See Exercise 31.4-4).

Let's figure out when when we have a colliding pair. We need to have:

$$h_b(k) = h_b(l)$$

Which is better written as:

$$h_b(k) - h_b(l) = 0 \mod p$$

Well, if we calculate the difference:

$$h_b(k) - h_b(l) = \sum_{j=0}^{n-1}{k_j b^j} - \sum_{j=0}^{n-1}{l_j b^j} = \sum_{j=0}^{n-1}{(k_j - l_j) b^j}$$

Which is a polynomial of the $(n-1)$-th degree. The referred exercise is a theorem, that tells us this polynomial would have a most $n-1$ zeroes modulo $p$.

There are $p$ possible functions, at most $n-1$ of which will cause any pair to have a collision, therefore:

$$\Pr\{ h(k) = h(l) \} \le \frac{n-1}{p}$$