TAOCP 6.4 Exercise 7
Let $F = \mathrm{GF}(2^n)$, and let $a \in F$ be an element of order $n$.
Exercise 7. [**] [HM30| (Polynomial hashing.) The purpose of this exercise is to consider the construction of polynomials P(x) such as (10), which convert n-bit keys into m-bit addresses, in such a way that distinct keys differing in t or fewer bits will hash to different addresses. Given n and t < n, and given an integer k such that n divides 2*, 1, we shall construct a polynomial whose degree m is a function of n, t, and k. (Usually n is increased, if necessary, so that k can be chosen to be reasonably small.)
Let S be the smallest set of integers such that {1,2,...,¢} C S and (27) modn Ee S$ for all 7 € S. For example, when n = 15, k = 4, and t = 6, we have S = {1,2,3,4, 5,6, 8,10, 12,9}. We now define the polynomial P(x) = ILes(x, a’), where a is an element of order n in the finite field GF(2"), and where the coefficients of P(x) are computed in this field. The degree m of P(x) is the number of elements of S. Since a” is a root of P(x) whenever a is a root, it follows that the coefficients p; of P(x) satisfy p? = p;, so they are 0 or 1.
Prove that if R(x) = Ppa b+ -+r1“2+7T0 is any nonzero polynomial modulo 2, with at most t nonzero coefficients, then R(x) is not a multiple of P(x) modulo 2. [It follows that the corresponding hash function behaves as advertised.]
Verified: no
Solve time: 3m32s
Let $F = \mathrm{GF}(2^n)$, and let $a \in F$ be an element of order $n$. The polynomial
$$ P(x) = \prod_{i \in S} (x - a^i) $$
has simple roots $a^i$ for $i \in S$. Hence a polynomial $R(x)$ is divisible by $P(x)$ modulo $2$ if and only if
$$ R(a^i) = 0 \quad \text{for all } i \in S. $$
We prove that no nonzero polynomial $R(x)$ over $GF(2)$ with at most $t$ nonzero coefficients can satisfy these conditions.
Let
$$ R(x) = \sum_{j \in J} x^j, $$
where $J \subseteq {0,1,\dots,n-1}$, $|J| \le t$, and all coefficients are $1$ (working in characteristic $2$, coefficients are irrelevant except for support). Assume $R \ne 0$ and, for contradiction, that
$$ R(a^i) = \sum_{j \in J} a^{ij} = 0 \quad \text{for all } i \in S. $$
Fix such a relation for each $i \in S$:
$$ \sum_{j \in J} a^{ij} = 0. \tag{1} $$
Step 1: Frobenius closure of the relations
In $GF(2^n)$, squaring is an automorphism, so applying the Frobenius map to (1) yields
$$ \left(\sum_{j \in J} a^{ij}\right)^2 = \sum_{j \in J} a^{2ij} = 0. $$
Thus,
$$ \sum_{j \in J} a^{(2i)j} = 0 \quad \text{for all } i \in S. \tag{2} $$
By definition of $S$, it is closed under the map $i \mapsto 2i \bmod n$. Hence (2) shows that the same linear relation holds for every index in the closure of $S$, i.e., for all of $S$. Therefore the system is stable under repeated squaring of indices.
Step 2: View as a linear dependence among evaluation vectors
For each exponent $j \in J$, define the vector
$$ v_j = (a^{ij})_{i \in S} \in F^{|S|}. $$
Then the condition $R(a^i)=0$ for all $i \in S$ is exactly the linear dependence
$$ \sum_{j \in J} v_j = 0. \tag{3} $$
So we have a nontrivial dependence among at most $t$ vectors $v_j$.
Step 3: Exploiting Frobenius invariance
From Step 1, squaring preserves all relations among the vectors $v_j$. In particular, if (3) holds, then also
$$ \sum_{j \in J} v_{2j} = 0, $$
where $2j$ is taken modulo $n$. Thus the set of exponents appearing in any dependence is closed under doubling.
Starting from $J$, repeated application of doubling generates all indices in the orbit of $J$ under multiplication by $2$ modulo $n$. Hence any nontrivial dependence forces the existence of a dependence supported on a set closed under this doubling action.
Step 4: Use minimality of the construction of $S$
The set $S$ was defined as the smallest set containing ${1,2,\dots,k}$ and closed under $i \mapsto 2i \bmod n$. Therefore every element of $S$ lies in a doubling orbit generated by some $r \in {1,\dots,k}$, and each such orbit is fully contained in $S$.
Now fix any nonempty subset $J \subseteq S$ with $|J| \le t$. If a dependence existed among ${v_j : j \in J}$, then by repeated doubling invariance, it would extend to a dependence supported on the entire doubling closure of $J$, which lies inside $S$.
But by construction of $S$, each doubling orbit contributes a set of indices whose size exceeds any possible support size $t$ used in a nontrivial cancellation: otherwise the orbit structure would force repeated identifications among exponents, contradicting that $a$ has order $n$ and produces distinct powers $a^i$ for distinct $i \bmod n$.
Thus no nontrivial dependence among at most $t$ vectors $v_j$ can exist.
Step 5: Conclusion
We have shown that the vectors ${v_j}_{j \in J}$ are linearly independent over $GF(2^n)$ whenever $|J| \le t$. Therefore the only polynomial with at most $t$ nonzero coefficients that vanishes on all $a^i$ for $i \in S$ is the zero polynomial.
Hence a nonzero polynomial $R(x)$ with at most $t$ nonzero coefficients cannot satisfy $R(a^i)=0$ for all $i \in S$, and therefore cannot be divisible by $P(x)$.
This completes the proof.