# Hash functions producing uniform outputs

I've seen this question in a past exam paper, and I know that the answer given is (b), but I'm not sure why.

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

(a) h(i) = i2 mod 10

(b) h(i) = i3 mod 10

(c) h(i) = (11 i2) mod 10

(d) h(i) = (12 i) mod 10

I understand the number of buckets relating to the modulus, but not how the factor or power of i affects the uniformity of the distribution.

What are the quadratic residues in $\mathbb{Z}_{10}$? What about the cubic residues? What are the orders of $[11]$ and $[12]$ in the group $(\mathbb{Z}_{10}, +)$?

A brief solution follows.

For the sake of clarity, we rename the four functions $a, b, c, d$. Let's analyze their range. Because of the closure properties of the modulo operation, we may do so in the ring $(\mathbb{Z}_{10}, +, \cdot)$. We will prove that $a, c, d$ have a range that is a strict subset of $\mathbb{Z}_{10}$, and can not therefore be uniform, while $b$ is a permutation of $\mathbb{Z}_{10}$.

Since we are working over a finite ring, we could compute each of the functions on each element of $\mathbb{Z}_{10}$ and prove our claim by exhaustion. Even though that's probably what the exercise wanted you to do, and what you should fall back on if you don't understand what follows, a true gentlemen never does that. Let's work out a more elegant way.

To begin with, we observe that $a(i) = i^2$ cannot be injective, and therefore, by piegonhole, not even surjective modulo any $m > 2$ as $[1] \neq [-1]$ but $[1]^2 = [1] = [-1]^2$. This also rules out $c$, since $[11] = [1]$ in $\mathbb{Z}_{10}$.

$d$ has to go as well; this stems from the more general fact, which I leave for you to prove, that if $\gcd(k, m) \neq 1$ then $f(i) = ki$ cannot be injective modulo $m$. (Hint: use the Bezout identity).

Now all is left is to prove that $b(i) = i^3$ is a permutation of $\mathbb{Z}_{10}$. First of all, we observe that the ring $\mathbb{Z}_{10}$ is isomorphic to the direct sum of $\mathbb{Z}_5$ and $\mathbb{Z}_2$. Since $b$ is clearly a permutation of $\mathbb{Z}_2$, if we prove that it's also a permutation of $\mathbb{Z}_5$ we are done. But $5$ is prime, so $i^3 \equiv i^{-1}$, which proves our claim.

• Sorry please could you elaborate, I don't quite understand how these concepts apply? Thanks for your answer – Rob Farr Jan 6 '17 at 13:19
• @RobFarr : I edited my answer with a more detailed explaination. – quicksort Jan 6 '17 at 15:25