# Proof the probability of a collision for a hash function

I don't know how to prove the following:

Let $$a$$ be randomly chosen out of $$\{ 1,..., p-1\}$$ and $$b$$ randomly chosen out of $$\{ 0,..., p-1\}$$. Let $$m$$ be a natural number smaller than a prime number $$p$$. Let $$h_{a,b}:$$ $$\{ 0,..., p-1\} \to \{0, ..., m-1 \}$$ which is defined as $$h_{a,b} = (ax + b \mod p) \mod m$$. Prove for all natural numbers $$x, y$$ with $$x < y < p$$: $$P_{a,b}(h_{a,b}(x)=h_{a,b}(y)) \le \frac{1}{m}$$ where $$P$$ is the probability.

• When asking a question like this, I encourage you to provide additional context, such as: Where did you encounter this task? What did you try, and what progress have you made? If you're stuck, working through a few examples with small numbers (e.g., with $p=3$ or $p=5$) is often useful for developing intuition.
– D.W.
Jun 28 at 22:06

Let $$k_{a,b}(x) = ax + b \bmod{p}$$. If $$x \neq y$$ then $$k_{a,b}(x), k_{a,b}(y)$$ is a random pair of distinct numbers in $$\{0,\ldots,p-1\}$$. Therefore we have reduced your question into the following one:
Show that if $$x \neq y$$ are random distinct numbers in $$\{0,\ldots,p-1\}$$, then $$\Pr[x \bmod m = y \bmod m] \leq \frac{1}{m}.$$
Suppose that $$p = dm + r$$, where $$1 \leq r \leq m-1$$. Then $$\Pr[x \bmod m = c]$$ is either $$d/p$$ (for $$c \ge r$$) or $$(d+1)/p$$ (for $$c < r$$). It follows that $$\Pr[x \bmod m = y \bmod m] = r \frac{(d+1)d}{p(p-1)} + (m-r) \frac{d(d-1)}{p(p-1)} = \frac{(p-m+r)d}{p(p-1)}.$$ Since $$r < m$$, we have $$\frac{p-m+r}{p-1} \leq 1$$. Also, $$\frac{d}{p} \leq \frac{d}{dm} = \frac{1}{m}$$. Altogether, we obtain an upper bound of $$\frac{1}{m}$$.
• Why is the probabillity for $\Pr[x \bmod m = c]$ either $d/p$ (for $c \ge r$) or $(d+1)/p$ (for $c < r$)? Jun 28 at 16:42
• And as a follow up question, shouldn't it be $m > r$ at the end because of the way you defined $r$? Jun 28 at 16:55
• Right, thanks for the correction. As for calculating the probability that $x \bmod m = c$, you'll have to work it out. Perhaps try some concrete numerical examples. Jun 28 at 18:35