Finding collision probability of hash function using modulo operation

Question

I have a hash function which maps elements from a set A to another set B. The size of the two sets are n and m respectively (with n >> m). The hash function is of the form -

$h: x' = x \; (mod \; m) \; | \; x \in A \;,\; x' \in B$

Thus, the elements in set B would be $\{0,1,2...(m-1)\}$. I want to compute the collision probability for any two elements in A ?

Any type of help would be highly appreciated.

Answer 1

The collision probability of Modulo hash function occurs for each couple of preimages located from a distance of $km$ for each integer $k<\frac{n}{m}$. But if $m$ doesn't divide $n$, there should be some side cases.

Let $k$ to be $\lfloor\frac{n}{m}\rfloor$

• For two elements where one's index is located beyond $km$, the number of eventualities sums to $\binom{1}{k}(n \mod[m])$
• If one element doesn't exceed this threshold or $m | n$, the occurences are just $\binom{2}{k}(m)$

To calculate the propability add up the two cases $P=P(Case_1)+P(Case_2)$ where $P(C_1\cap C_2)=0$ , the number to divide on is $\binom{1}{km}$ for the first case and $\binom{2}{km}$ in the other case.