TAOCP 4.6.2 Exercise 36

Let u(x)=\prod_{i\ge1} u_i(x)^i be the squarefree representation of the given polynomial modulo $p$.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.2: Factorization of Polynomials

Exercise 36. [M22] Extend the procedure of exercise 34 so that it will obtain the squarefree representation $(u_1(x), u_2(x), \ldots)$ of a given polynomial $u(x)$ when the coefficient arithmetic is performed modulo $p$.

Verified: yes
Solve time: 2m33s

Solution

Let

$$ u(x)=\prod_{i\ge1} u_i(x)^i $$

be the squarefree representation of the given polynomial modulo $p$. The difficulty, compared with Exercise 34, is that the derivative may vanish even when repeated factors are present, because

$$ \bigl(f(x)\bigr)^p=f(x^p) $$

and therefore

$$ \frac{d}{dx}\bigl(f(x)^p\bigr)=0 . $$

Hence the procedure over the integers must be modified to account for factors whose multiplicities are divisible by $p$.

Write

$$ u(x)=\prod_j P_j(x)^{e_j}, $$

where the $P_j$ are distinct monic irreducible polynomials. Let

$$ e_j=q_jp+r_j,\qquad 0\le r_j<p . $$

Then

$$ u(x) = \left(\prod_j P_j(x)^{q_j}\right)^p \prod_j P_j(x)^{r_j}. \tag{1} $$

The second factor contains exactly those multiplicities not divisible by $p$.

Let

$$ d(x)=\gcd(u(x),u'(x)). $$

Since

$$ u'(x) = \sum_j e_j P_j(x)^{e_j-1}P_j'(x) \prod_{k\ne j}P_k(x)^{e_k}, $$

and $P_j'(x)\ne0$ for every irreducible factor that is not itself a $p$th power, the exponent of $P_j$ in $d(x)$ is

$$ \begin{cases} e_j-1,& r_j\ne0,\[2mm] e_j,& r_j=0. \end{cases} $$

Consequently, if

$$ \text{GCD}(u,u') =(d,a,b), $$

so that

$$ u=d,a,\qquad u'=d,b, $$

then

$$ a(x)=\prod_{r_j\ne0}P_j(x). \tag{2} $$

Thus $a(x)$ is squarefree and contains precisely the irreducible factors whose multiplicities are not divisible by $p$.

Now form

$$ c(x)=\frac{d(x)}{\gcd(a(x),d(x))}. \tag{3} $$

For each $P_j$ with $r_j\ne0$, the exponent in $d$ is $e_j-1$ and the exponent in $\gcd(a,d)$ is $1$; hence the exponent in $c$ is $e_j-2$. For each $P_j$ with $r_j=0$, the exponent in $\gcd(a,d)$ is $0$, so the exponent in $c$ is $e_j$. Therefore

$$ c(x) = \prod_{r_j\ne0}P_j(x)^{e_j-2} \prod_{r_j=0}P_j(x)^{e_j}. \tag{4} $$

Exactly as in Exercise 34, the squarefree factors corresponding to multiplicities $1,2,\ldots,p-1$ can be extracted from the pair $(a,c)$ by repeated gcd computations. Let

$$ a_1=a,\qquad c_1=c. $$

For $i=1,2,\ldots,p-1$, compute

$$ \text{GCD}(a_i,c_i)=(g_i,a_{i+1},c_{i+1}). \tag{5} $$

Then $g_i$ is the product of all irreducible factors whose multiplicity in $u$ is exactly $i$ modulo $p$.

After these $p-1$ stages, all factors with multiplicity not divisible by $p$ have been separated. The remaining polynomial is

$$ c_p(x) = \prod_{r_j=0}P_j(x)^{q_jp}. \tag{6} $$

Every exponent of $c_p$ is a multiple of $p$; hence

$$ c_p(x)=w(x)^p $$

for a unique polynomial $w(x)$. By equation (5) of the text,

$$ c_p(x)=v(x^p) $$

and $w(x)=v(x)$. Therefore $w$ is obtained simply by replacing each term

$$ a_kx^{kp} $$

by

$$ a_kx^k. $$

The squarefree representation of $w$ is then computed recursively. If

$$ w(x)=\prod_{i\ge1} t_i(x)^i, $$

then

$$ c_p(x)=w(x)^p =\prod_{i\ge1} t_i(x)^{ip}, $$

so every factor $t_i$ contributes to multiplicity $ip$ in $u$.

The complete algorithm is therefore:

Given $u(x)$:

  1. Compute $\text{GCD}(u,u')=(d,a,b)$.
  2. If $u'=0$, write $u(x)=v(x^p)$, recursively factor $v$, and multiply all subscripts in the resulting squarefree representation by $p$.
  3. Otherwise form $c=d/\gcd(a,d)$.
  4. Repeatedly apply (5) for $i=1,\ldots,p-1$. The factors $g_i$ obtained are exactly the squarefree components whose multiplicities are congruent to $i$ modulo $p$.
  5. The remaining polynomial $c_p$ is a perfect $p$th power. Write $c_p=w^p$, recursively compute the squarefree representation $(t_1,t_2,\ldots)$ of $w$, and place each $t_i$ into position $ip$.
  6. Multiply together factors assigned to the same index.

Correctness follows from the multiplicity analysis above. Steps 1, 3, and 4 separate all irreducible factors according to their residue class modulo $p$; Step 5 reduces every multiplicity divisible by $p$ by a factor of $p$ and applies the same argument recursively. Since each recursion lowers the degree by a factor of $p$, the process terminates. The resulting sequence $(u_1,u_2,\ldots)$ contains exactly those irreducible factors occurring with multiplicity $1,2,\ldots$, respectively, and therefore is the desired squarefree representation.

This completes the proof.

∎