TAOCP 7.1.3 Exercise 67

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 67. [M31] If $u(x)$ is a polynomial of degree $< n$, represented as in exercise 65, discuss the computation of $v(x) = u(x)^2 \bmod (x^n + x^m + 1)$, when $0 < m < n$ and both $m$ and $n$ are odd. Hint: This problem has an interesting connection with perfect shuffling.

Verified: no
Solve time: 1m01s

---

Setup

Work in the ring $\mathbb{F}_2[x]/(x^n + x^m + 1)$ with $0<m<n$, where $m$ and $n$ are odd. A polynomial

$u(x)=\sum_{i=0}^{n-1} u_i x^i$

is represented by the bit vector $(u_{n-1}\ldots u_0)2$, and by the integer $u=(u{n-1}\ldots u_0)_2$ as in exercise 65.

We must compute

$v(x)=u(x)^2 \bmod (x^n+x^m+1).$

Since the characteristic is $2$,

$(a+b)^2 = a^2 + b^2,$

so cross terms vanish and

$u(x)^2 = \sum_{i=0}^{n-1} u_i x^{2i}.$

Thus the problem reduces to reducing each monomial $x^{2i}$ modulo $x^n = x^m + 1$.

Solution

Define the linear operator $T$ on polynomials by

$T(p(x)) = x \cdot p(x) \bmod (x^n + x^m + 1).$

Then $T(x^k)=x^{k+1}$ for $k<n-1$, and from $x^n=x^m+1$,

$T(x^{n-1}) = x^n = x^m + 1 = x^m + x^0.$

Hence multiplication by $x$ acts on the basis ${1,x,\dots,x^{n-1}}$ as

$x^k \mapsto x^{k+1} \ (k<n-1), \qquad x^{n-1} \mapsto x^m + x^0.$

For any exponent $t$, write

$x^t \equiv T^t(1).$

Therefore,

$x^{2i} \equiv T^{2i}(1).$

Let $e_k$ denote the unit vector corresponding to $x^k$. Then

$v = \sum_{i=0}^{n-1} u_i , T^{2i}(e_0).$

Thus the squaring map is the linear transformation whose matrix is obtained by applying the “doubling map” $i \mapsto 2i$ to the action of $T$.

Now express $T$ as a permutation-with-feedback on indices. For $0 \le k \le n-2$, $T$ sends $k \mapsto k+1$, and for $k=n-1$, the index splits as

$n-1 \mapsto m \oplus 0.$

Iterating this rule shows that each application of $T$ corresponds to advancing a token around a cyclic structure of length $n$, except that when passing position $n-1$, the state branches and adds a shifted copy at position $m$.

Because all operations are linear over $\mathbb{F}_2$, the image of a basis vector under $T^{2i}$ is determined solely by the binary expansion of $2i$, i.e., by repeated squaring of the shift action. This is exactly the structure of a perfect shuffle on $n$ positions with a wrap-around offset $m$: doubling indices permutes the cyclic order, and the wrap at $n$ injects a fixed shift by $m$.

Consequently, the squaring map is a permutation of the coefficient vector $(u_0,\dots,u_{n-1})$: each output coefficient $v_k$ is the XOR of exactly one input coefficient $u_i$, where $i$ is determined by the unique index satisfying

$T^{2i}(1)=x^k.$

Thus the transformation $u \mapsto v$ is a permutation of bits induced by the doubling map on the cycle generated by $T$, i.e., by the perfect shuffle determined by the affine rule

$k \mapsto 2k \pmod n \quad \text{with carry producing a shift by } m.$

Verification

The reduction rule $x^n = x^m + 1$ implies every monomial $x^{2i}$ reduces to a linear combination of basis elements obtained by repeatedly replacing occurrences of $x^n$ with $x^m + 1$. Each replacement is linear over $\mathbb{F}_2$, so the final expression for $x^{2i}$ is a sum of distinct basis monomials.

Because squaring in characteristic $2$ eliminates cross terms, contributions from different $u_i$ do not interact except through XOR, so the mapping from $u$ to $v$ is linear over $\mathbb{F}_2$.

Since $T$ is invertible (its action corresponds to a permutation of the $n$-dimensional state space induced by a cyclic shift with a single feedback at $n-1$), each $T^{2i}(1)$ is distinct for different $i$, so the resulting linear transformation sends basis vectors to a permutation of basis vectors. Hence each output bit depends on exactly one input bit.

Conclusion

The mapping $u(x) \mapsto u(x)^2 \bmod (x^n + x^m + 1)$ is the linear permutation of the coefficient vector induced by doubling indices under the shift-with-feedback rule defined by $x^n = x^m + 1$. Equivalently, it is the perfect shuffle permutation on ${0,\dots,n-1}$ generated by $i \mapsto 2i$ with wrap-around offset $m$. ∎