Question 43

We evaluate each function for $i \in \{0, 1, \dots, 9\}$:

• (A) $h(i) = i^2 \bmod 10$:
  Squares modulo 10 can only take values in $\{0, 1, 4, 5, 6, 9\}$. Only 6 out of 10 buckets are used; buckets 2, 3, 7, 8 receive 0 keys.

• (B) $h(i) = i^3 \bmod 10$:
  Computing cubes modulo 10:

  $$0^3 \equiv 0,\; 1^3 \equiv 1,\; 2^3 \equiv 8,\; 3^3 \equiv 7,\; 4^3 \equiv 4,$$
  $$5^3 \equiv 5,\; 6^3 \equiv 6,\; 7^3 \equiv 3,\; 8^3 \equiv 2,\; 9^3 \equiv 9.$$

  Every digit in $\{0, 1, 2, \dots, 9\}$ is hit exactly once! Thus, $i^3 \bmod 10$ is a permutation polynomial on $\mathbb{Z}_{10}$, distributing keys with perfect uniformity across all 10 buckets.

• (C) $h(i) = (11 \times i^2) \bmod 10 \equiv i^2 \bmod 10$: identical to (A), only 6 buckets used.

• (D) $h(i) = (12 \times i) \bmod 10 \equiv 2i \bmod 10$: produces only even values $\{0, 2, 4, 6, 8\}$; odd buckets receive 0 keys.

Therefore, $h(i) = i^3 \bmod 10$ achieves the most uniform distribution (option B).