TAOCP 4.6.2 Exercise 26

Let $u(x)=p_1(x)^{e_1}\cdots p_r(x)^{e_r}$ be the factorization of $u(x)$ modulo $p$, and let $d_j=\deg p_j(x)$ for $1\le j\le r$, with multiplicities included.

taocpmathematicsalgorithmsvolume-2

Section 4.6.2: Factorization of Polynomials

Exercise 26. [**] [20] Let $d_1, \ldots, d_r$ be the degrees of the irreducible factors of $u(x)$ modulo $p$, with proper multiplicity, so that $d_1 + \cdots + d_r = \deg(u)$. Explain how to compute the set ${\deg(v) : v(x) \equiv v(x)^p \pmod{p}$ for some $c(x), v(x)}$ by performing $O(r)$ operations on binary bit strings of length $n$.

Verified: yes
Solve time: 4m05s

Let

$u(x)=p_1(x)^{e_1}\cdots p_r(x)^{e_r}$

be the factorization of $u(x)$ modulo $p$, and let

$d_j=\deg p_j(x)$

for $1\le j\le r$, with multiplicities included. By the discussion following equation (8), the solutions of

$v(x)^p\equiv v(x)\pmod{u(x)}$

form a vector space of dimension $r$ over $\mathbf F_p$, and each irreducible factor contributes one independent choice of residue class modulo that factor. Hence the possible degrees of such polynomials are exactly the subset sums

$\Bigl{\sum_{j\in S} d_j : S\subseteq{1,\ldots,r}\Bigr}.$

These values can be computed by the standard bit-string method for subset sums. Represent a set $A\subseteq{0,\ldots,n}$ by a binary string

$(b_0,b_1,\ldots,b_n),$

where $b_k=1$ iff $k\in A$. Initialize

$B\leftarrow(1,0,\ldots,0),$

representing the set ${0}$. Then for $j=1,\ldots,r$ perform

$B\leftarrow B\lor(B\ll d_j),$

where $\ll d_j$ denotes left shift by $d_j$ positions and $\lor$ denotes bitwise OR. After the $j$th step, the 1-bits represent all subset sums obtainable from $d_1,\ldots,d_j$. Therefore after $r$ such operations, the 1-bits occur exactly in the positions

$\sum_{j\in S} d_j,$

which are precisely the desired degrees. Since each step uses one shift and one OR on bit strings of length $n=\deg(u)$, the total work is $O(r)$ bit-string operations.