1
$\begingroup$

I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following excerpt regarding the said proof and the steps where I felt difficulty are marked with $\dagger$ and $\dagger\dagger$ respectively.

Designing a universal class of hash functions

$p$ is a prime number large enough so that every possible key $k$ is in the range $0$ to $p — 1$, inclusive. Let $Z_p$ denote the set $\{0, 1,..., p — 1\}$, and let $Z_p^*$ denote the set $\{1, 2,..., p — 1\}$.Because of the assumption that the size of the universe of keys is greater than the number of slots $m$ in the hash table, we have $p > m$.

We now define the hash function $h_{a,b}$ for any $a \in Z_p^*$ and any $b \in Z_p$ :

$h_{a,b} = ((a.k + b) \mod p) \mod m $.

The family of all such hash functions:

$$\mathscr{H}_{p,m}=\{h_{a,b}: a \in Z_p^* , b \in Z_p\}$$


Theorem: The class $\mathscr{H}_{p,m}$ of hash functions is universal.


Proof:

Consider two distinct keys $k$ and $l$ from $Z_p$, so that $k \neq l$. For a given hash function $h_{a,b}$ we let

$$r = (ak + b) \mod p$$ ,

$$s = (al + b) \mod p $$.

We first note that $r\neq s$. Why? Observe that

$$r — s = a(k — l) (\mod p)$$ .

It follows that $г \neq s$ because $p$ is prime and both $a$ and $(k — l)$ are nonzero modulo $p$, and so their product must also be nonzero modulo $p$

Therefore, during the computation of any $h_{a,b}$ in $\mathscr{H}_{p,m}$, distinct inputs $k$ and $l$ map to distinct values $r$ and $s$ modulo $p$; there are no collisions yet at the "mod p level." Moreover, each of the possible $p(p — 1)$ choices for the pair $(a, b)$ with $а \neq 0$ yields a different resulting pair $(r, s)$ with $r \neq s$, since we can solve for $a$ and $b$ given $r$ and $s$$^\dagger$:

$$a = ((r — s)((k — l)^{-1}\mod p)) \mod p $$,

$$b = (r — ak) \mod p$$ ,

where $((k — l)^{-1} \mod p)$ denotes the unique multiplicative inverse, modulo p, of $k — l$. Since there are only $p(p — 1)$ possible pairs $(r, s)$ with $г \neq s$, there is a one-to-one correspondence between pairs $(a, b)$ with $a \neq 0$ and pairs $(r, s)$ with $r \neq s$. Thus, for any given pair of inputs $k$ and $l$, if we pick $(a, b)$ uniformly at random from $Z_p^* \times Z_p$, the resulting pair $(r, s)$ is equally likely to be any pair of distinct values modulo p.

It then follows that the probability that distinct keys $k$ and $l$ collide is equal to the probability that $r \equiv s (\mod m)$ when $r$ and $s$ are randomly chosen as distinct values modulo $p$. For a given value of $r$, of the $p — 1$ possible remaining values for $s$, the number of values $s$ such that $s \neq r$ and $s \equiv r (\mod m)$ is at most$^{\dagger\dagger}$

$$\lceil p/m \rceil - 1 < ((p + m - 1)/m) - 1$$ $$ =(p-1)/m$$.

The probability that $s$ collides with $r$ when reduced modulo $m$ is at most $((p - l)/m)/(p - 1) = 1/m$.

Therefore, for any pair of distinct values $k,l \in Z_p$,

$$Pr\{h_{a,b}(k)=h_{a,b}(l)\}\leq 1/m$$

so that $\mathscr{H}_{p,m}$ is indeed universal.


Doubts:

I could not understand the following statements in the proof:

$\dagger$ :Each of the possible $p(p — 1)$ choices for the pair $(a, b)$ with $а \neq 0$ yields a different resulting pair $(r, s)$ with $r \neq s$, since we can solve for $a$ and $b$ given $r$ and $s$

why , "we can solve for $a$ and $b$ given $r$ and $s$" $\implies$ "Each of the possible $p(p — 1)$ choices for the pair $(a, b)$ with $а \neq 0$ yields a different resulting pair $(r, s)$ with $г \neq s$"


$\dagger\dagger$ : For a given value of $r$, of the $p — 1$ possible remaining values for $s$, the number of values $s$ such that $s \neq r$ and $s \equiv r (\mod m)$ is at most $\lceil p/m \rceil - 1 $ .

How do we get the term $\lceil p/m \rceil - 1 $ ?

$\endgroup$
2
$\begingroup$

We want to show that if $k_1\neq k_2\in\mathbb{Z}_p$ then

$\Pr\limits_{(a,b)\in\mathbb{Z}_p^*\times\mathbb{Z}_p}[ak_1+b\equiv ak_2+b \pmod m]\le\frac{1}{m}$.

Where both addition and multiplication are preformed in $\mathbb{Z}_p$.

We start by showing that if $a\sim U(Z_p^*)$ and $b\sim U(Z_p)$ then for all $k_1\neq k_2\in \mathbb{Z}_p$, $(ak_1+b,ak_2+b)$ is uniformly distributed over $\{(x,y)\in\mathbb{Z}_p^2| x\neq y\}$ (i.e. $h(k_1)$ and $h(k_2)$ are jointly uniform over pairs with different entries, where the randomness is over the choice of $h$). This is immediate from the fact that for all $(c_1,c_2)\in\mathbb{Z}_p^2$ with $c_1\neq c_2$, the following system of linear equations:

$ \begin{align*} & ak_1+b=c_1 \\ & ak_2+b=c_2 \end{align*} $

has a unique solution over the variables $(a,b)\in Z_p^*\times\mathbb{Z}_p$. Subtracting the second equation from the first yields $a(k_1-k_2)=c_1-c_2$, since $k_1-k_2$ is nonzero we can multiply both sides by its inverse and obtain $a=(k_1-k_2)^{-1}(c_1-c_2)$. If $c_1\neq c_2$, then this is a nonzero solution for $a$, and we can extract $b$ from any of the two equations. Thus, for each pair $(c_1,c_2)$ with $c_1\neq c_2$ there are unique $(a,b)\in Z_p^*\times\mathbb{Z}_p$ such that $\big(h_{a,b}(k_1),h_{a,b}(k_2)\big)=(c_1,c_2)$. This settles your first question.

Now, divide $\mathbb{Z}_p$ into $\lceil p/m\rceil$ buckets, $b_1,...,b_{l=\lceil p/m\rceil}$ as follows: $b_1=\{0,1,...,m-1\}, b_2=\{m,m+1,...,2m-1\}$,...,$b_l=\{m\lfloor p/m\rfloor, m\lceil p/m\rceil+1,...,p-1\}$. Note that each bucket except the last is of size $m$, and no two elements in the same bucket are equivalent modulo $m$. We conclude that the number of different pairs in $\{(x,y)\in\mathbb{Z}_p^2| x\neq y\}$ that are equivalent modulo $m$ is at most $p(\lceil p/m\rceil-1)$, since after choosing the first element, you are left with $\lceil p/m\rceil-1$ elements to choose from (you must pick a different bucket and each bucket provides at most one candidate). Recall that $\big(h_{a,b}(k_1),h_{a,b}(k_2)\big)\sim U(\{(x,y)\in\mathbb{Z}_p^2| x\neq y\})$, so we can finally conclude:

$\Pr\limits_{(a,b)\in\mathbb{Z}_p^*\times\mathbb{Z}_p}\left[h_{a,b}(k_1)=h_{a,b}(k_2)\pmod m\right]=\frac{p(\lceil p/m\rceil-1)}{p(p-1)}\le \frac{1}{m}$

Note that allowing $a$ to take the value $0$ only makes our analysis easier, since now $\big(h(k_1),h(k_2)\big)$ is jointly uniform over $\mathbb{Z}_p^2$, but there is an additionaly probability of $\frac{1}{p}$ that $a=0$ and our hashes will be equivalent modulo $m$, so in this case we will have to settle for an $O(\frac{1}{m})$ bound on the collision probability.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $\dagger\dagger$ logic is great. Thanks for the help. From your $\dagger$ I got the point of the authors, they are trying to show the bijection property. Already they had shown that $(a,b)$ produced unique soln $(r,s)$ and in the $\dagger$ part they are trying to show that $(r,s)$ gives unique $(a,b)$.. Now in your logic of the $\dagger$ there are few things I do not get... (1) The meaning of notation $a\sim U(Z_p^*)$ (2) what is hash fn. $h(k)$ (3) did you mean linear eqn or congruence? It possible $c_1 \neq c_2$ but $c_1 \equiv c_2 (\mod p)$, or you just tried to make me understand? $\endgroup$ – Abhishek Ghosh Jun 26 at 7:03
  • 1
    $\begingroup$ I used $x\sim U(A)$ to denote that $x$ is uniformly distributed over the set $A$. Anywhere $h$ should read as $h_{a,b}$. We can reason about a system of linear equation in any field. Here instead of the usual $\mathbb{R}$ the variables and coefficients all lie in the finite field $\mathbb{Z}_p$. $\endgroup$ – Ariel Jun 26 at 8:01
  • $\begingroup$ One more query. I hope (that to simplify the situation) you have chosen $h_{a,b}=ak+b$ is it so? That is why there is attempt to show that $Pr\{h_{a,b}(k_1)=h_{a,b}(k_2) (\mod m)\}\leq 1/m$ unlike $h_{a,b}(k) = ((a.k + b)\mod p)\mod m)$ as the book assumed... $\endgroup$ – Abhishek Ghosh Jun 26 at 8:17
  • 1
    $\begingroup$ The universal family discussed here is $\mathcal{H}=\{h_{a,b}|a,b\in\mathbb{Z}_p\}$ where $h(a,b):\mathbb{Z}_p\rightarrow\mathbb{Z}_p$ is defiend by $h_{a,b}(k)=ak+b$, where the operations are preformed in $\mathbb{Z}_p$ (so the $\bmod p$ isn't really gone if that's what bothers you, it's just a redundant notation when you work in a finite field). $\endgroup$ – Ariel Jun 26 at 8:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.