1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

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

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.