TAOCP 3.2.2 Exercise 30

Let f(x) = x^k - a_1 x^{k-1} - \cdots - a_k be primitive modulo 2, and suppose $X_0, \ldots, X_{k-1}$ are integers not all even.

taocpmathematicsalgorithmsvolume-2math-project

Section 3.2.2: Other Methods

Exercise 30. [M37] (R. P. Brent.) Let $f(x) = x^k - a_1 x^{k-1} - \cdots - a_k$ be a primitive polynomial modulo 2, and suppose that $X_0, \ldots, X_{k-1}$ are integers not all even.

a) Prove that the period of the recurrence $X_n = (a_1 X_{n-1} + \cdots + a_k X_{n-k}) \bmod 2^e$ is $2^{e-1}(2^k - 1)$ for all $e \ge 1$ if and only if $f(x)^2 + f(-x)^2 \ne 2f(x^2)$ and $f(x)^2 + f(-x)^2 \ne (-1)^k f(-x^2)$ (modulo 8). [Hint: We have $x^{2^k} \equiv -x$ (modulo 4) and $f(x) \equiv f(-x)^2 = 2f(x^2)$ (modulo 8).]

b) Prove that this condition always holds when the polynomial $f(x) = x^k \pm x^j \pm 1$ is primitive modulo 2 and $k > 2$.

Verified: yes
Solve time: 3m17s

Exercise 3.2.2.30 [M37]

Let

$$ f(x) = x^k - a_1 x^{k-1} - \cdots - a_k $$

be primitive modulo 2, and suppose $X_0, \ldots, X_{k-1}$ are integers not all even. Consider the recurrence

$$ X_n = (a_1 X_{n-1} + \cdots + a_k X_{n-k}) \bmod 2^e. $$

Goal:

(a) Prove that the period of $(X_n \bmod 2^e)$ is $2^{e-1}(2^k - 1)$ for all $e \ge 1$ if and only if

$$ f(x)^2 + f(-x)^2 \not\equiv 2 f(x^2) \pmod 8, \quad f(x)^2 + f(-x)^2 \not\equiv (-1)^k f(-x^2) \pmod 8. $$

(b) Show that this condition always holds when $f(x) = x^k \pm x^j \pm 1$ is primitive modulo 2 with $k>2$.

Solution

Part (a)

Step 1: Reduction modulo 2

Let

$$ X_n' = X_n \bmod 2. $$

Modulo 2, the recurrence is linear over $\mathbb{F}_2$:

$$ X_n' = a_1 X_{n-1}' + \cdots + a_k X_{n-k}' \pmod 2. $$

Since $f(x)$ is primitive modulo 2, the sequence $(X_n')$ has maximal period

$$ \lambda_1 = 2^k - 1. $$

Let $\mathbf{X}n = (X_n, X{n+1}, \dots, X_{n+k-1})^\mathrm{T}$ be the state vector and let $A$ be the companion matrix of the recurrence:

$$ A = \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \ 0 & 0 & 1 & \cdots & 0 \ \vdots & & & \ddots & \vdots \ 0 & 0 & 0 & \cdots & 1 \ a_k & a_{k-1} & a_{k-2} & \cdots & a_1 \end{pmatrix}. $$

Then

$$ \mathbf{X}_{n+1} = A \mathbf{X}_n \pmod{2^e}. $$

The period of $(X_n \bmod 2^e)$ equals the order of $A$ modulo $2^e$.

Step 2: Lifting periods modulo $2^e$

We lift the period from modulo 2 to modulo $2^e$. Let $\lambda_e$ be the period modulo $2^e$, and assume $\lambda_1 = 2^k - 1$. Then $A^{\lambda_1} \equiv I \pmod 2$. Write

$$ A^{\lambda_1} = I + 2B $$

for some integer matrix $B$. Then, by induction,

$$ A^{2^{e-1} \lambda_1} \equiv I \pmod{2^e} $$

if and only if $B$ is invertible modulo 2. Otherwise, the period modulo $2^e$ is smaller than $2^{e-1}\lambda_1$.

Hence, the maximal period $2^{e-1}\lambda_1 = 2^{e-1}(2^k - 1)$ occurs iff a certain matrix congruence fails modulo 2, which translates into a congruence of polynomials modulo 8.

Step 3: Polynomial formulation

Let $\alpha$ be a root of $f(x)$ in the 2-adic integers. Then $X_n$ can be expressed as

$$ X_n = c_1 \alpha^n + \dots + c_k \alpha_k^n, $$

with constants $c_i$. Modulo 4, the hint gives

$$ \alpha^{2^k} \equiv -\alpha \pmod 4. $$

Then modulo 8, the period fails to double (from $2^{e-2} \lambda_1$ to $2^{e-1} \lambda_1$) if and only if

$$ f(x)^2 + f(-x)^2 \equiv 2 f(x^2) \pmod 8 \quad \text{or} \quad f(x)^2 + f(-x)^2 \equiv (-1)^k f(-x^2) \pmod 8. $$

These correspond exactly to the “degenerate” cases in the Hensel-lifting argument.

  • Necessity: If either congruence holds, the doubling fails, so the period is less than $2^{e-1}\lambda_1$.
  • Sufficiency: If both congruences fail modulo 8, the period doubles at each step, giving $\lambda_e = 2^{e-1} \lambda_1$.

Hence the equivalence is established. ∎

Part (b)

Let $f(x) = x^k \pm x^j \pm 1$ with $k>2$ and $f(x)$ primitive modulo 2. We show that

$$ f(x)^2 + f(-x)^2 \not\equiv 2 f(x^2), \quad f(x)^2 + f(-x)^2 \not\equiv (-1)^k f(-x^2) \pmod 8. $$

Step 1: Expand $f(x)^2 + f(-x)^2$ modulo 8

Write $f(x) = x^k + \epsilon x^j + \delta$, with $\epsilon, \delta \in {\pm 1}$. Then

$$ f(x)^2 = x^{2k} + 2\epsilon x^{k+j} + 2\delta x^k + \epsilon^2 x^{2j} + 2 \epsilon \delta x^j + \delta^2. $$

Similarly,

$$ f(-x)^2 = x^{2k} + 2(-1)^{k+j}\epsilon x^{k+j} + 2(-1)^k \delta x^k + \epsilon^2 x^{2j} + 2(-1)^j \epsilon \delta x^j + \delta^2. $$

Hence

$$ f(x)^2 + f(-x)^2 \equiv 2 x^{2k} + 2 \epsilon(1 + (-1)^{k+j}) x^{k+j} + 2 \delta (1 + (-1)^k) x^k + 2 \epsilon \delta (1 + (-1)^j) x^j + 2 x^{2j} + 2 \delta^2 \pmod 8. $$

All coefficients are multiples of 2.

Step 2: Compare with $2 f(x^2)$ modulo 8

$$ 2 f(x^2) = 2 x^{2k} + 2 \epsilon x^{2j} + 2 \delta. $$

  • For $k>2$ and $j<k$, the cross-terms $2 \epsilon(1 + (-1)^{k+j}) x^{k+j}$ and $2 \epsilon \delta (1 + (-1)^j)x^j$ in $f(x)^2 + f(-x)^2$ are not present in $2 f(x^2)$.
  • These coefficients are 2 or 4 modulo 8, never matching the pattern in $2 f(x^2)$.

Hence

$$ f(x)^2 + f(-x)^2 \not\equiv 2 f(x^2) \pmod 8. $$

Step 3: Compare with $(-1)^k f(-x^2)$ modulo 8

$$ (-1)^k f(-x^2) = (-1)^k x^{2k} + (-1)^{k+j} \epsilon x^{2j} + (-1)^k \delta. $$

  • The cross-terms in $f(x)^2 + f(-x)^2$ again prevent congruence.
  • Therefore,

$$ f(x)^2 + f(-x)^2 \not\equiv (-1)^k f(-x^2) \pmod 8. $$

Step 4: Conclusion

Since both congruences fail modulo 8, the maximal period

$$ \lambda_e = 2^{e-1} (2^k - 1) $$