TAOCP 4.6.2 Exercise 35
Let u(x)=u_1(x)u_2(x)^2u_3(x)^3\cdots u_e(x)^e, where the $u_i(x)$ are squarefree and pairwise relatively prime, and where $u_e(x)\ne1$.
Section 4.6.2: Factorization of Polynomials
Exercise 35. [M22] (D. Y. Y. Yun.) Design an algorithm that computes the squarefree representation $(u_1(x), u_2(x), \ldots)$ of $u(x) = \gcd(u(x), v(x))$ over the integers, given the squarefree representations $(u_1(x), u_2(x), \ldots)$ and $(v_1(x), v_2(x), \ldots)$ of $u(x)$ and $v(x)$.
Verified: yes
Solve time: 2m53s
Solution
Let
$$ u(x)=u_1(x)u_2(x)^2u_3(x)^3\cdots u_e(x)^e, $$
where the $u_i(x)$ are squarefree and pairwise relatively prime, and where $u_e(x)\ne1$.
Write
$$ w_i(x)=u_i(x)u_{i+1}(x)\cdots u_e(x) \qquad (1\le i\le e). $$
Then
$$ u(x)=w_1(x)w_2(x)\cdots w_e(x), $$
and
$$ w_i(x)=\prod_{j\ge i}u_j(x) $$
is squarefree for every $i$.
The problem is to recover the $u_i(x)$ using exactly $e$ computations of
$$ \text{GCD}(a,b) =\bigl(d,;a/d,;b/d\bigr), \qquad d=\gcd(a,b), $$
with each gcd satisfying condition (27), namely that the two arguments are relatively prime after division by the gcd.
We first derive a recurrence.
Since
$$ u(x)=\prod_{i=1}^{e}u_i(x)^i, $$
its derivative is
$$ u'(x) =\sum_{i=1}^{e} i,u_i(x)^{,i-1}u_i'(x) \prod_{j\ne i}u_j(x)^j. $$
Every irreducible factor occurring in $u_i(x)$ appears in $u'(x)$ with multiplicity at least $i-1$ and with multiplicity exactly $i-1$. Therefore
$$ \gcd(u,u') =u_2u_3^2u_4^3\cdots u_e^{,e-1}. $$
Hence
$$ \frac{u}{\gcd(u,u')} =u_1u_2\cdots u_e =w_1, $$
and
$$ \frac{\gcd(u,u')}{u/\gcd(u,u')} =u_2u_3^2\cdots u_e^{,e-2}. $$
Define
$$ c_1=u,\qquad b_1=u'. $$
For $i\ge1$ perform
$$ (d_i,a_i,c_{i+1}) =\text{GCD}(c_i,b_i). $$
Then
$$ d_i=\gcd(c_i,b_i), \qquad a_i=\frac{c_i}{d_i}, \qquad c_{i+1}=\frac{b_i}{d_i}. $$
For $i=1$,
$$ a_1=w_1. $$
Furthermore,
$$ c_2 =u_2u_3^2\cdots u_e^{,e-2}. $$
Assume inductively that
$$ c_i =u_i,u_{i+1}^2\cdots u_e^{,e-i+1}. \tag{1} $$
Since $c_i$ has the same form as the original polynomial but with exponents
$1,2,\ldots,e-i+1$, the same argument used above gives
$$ a_i =u_iu_{i+1}\cdots u_e =w_i, \tag{2} $$
and
$$ c_{i+1} =u_{i+1}u_{i+2}^2\cdots u_e^{,e-i}. \tag{3} $$
Thus (1) holds for $i+1$. By induction, after the $i$th gcd computation,
$$ a_i=w_i \qquad (1\le i\le e), $$
and
$$ c_{e+1}=1. $$
The squarefree factors are now obtained from the relations
$$ w_i=u_iw_{i+1}, \qquad 1\le i<e. $$
Because
$$ u_i=\frac{w_i}{w_{i+1}}, $$
and because $w_{i+1}\mid w_i$, no further gcd computations are needed. Set
$$ u_e=w_e=a_e, $$
and for $1\le i<e$ compute
$$ u_i=\frac{a_i}{a_{i+1}}. $$
The complete algorithm is therefore:
- Set $c_1=u$, $b_1=u'$.
- For $i=1,2,\ldots,e$ compute
$$ (d_i,a_i,c_{i+1}) =\text{GCD}(c_i,b_i), $$
and then set
$$ b_{i+1}=c_{i+1}'. $$ 3. Set
$$ u_e=a_e, $$
and for $i=e-1,e-2,\ldots,1$ set
$$ u_i=\frac{a_i}{a_{i+1}}. $$
Exactly $e$ gcd computations are performed. At the $i$th stage,
$$ a_i=\frac{c_i}{\gcd(c_i,b_i)}, \qquad c_{i+1}=\frac{b_i}{\gcd(c_i,b_i)}, $$
so the two cofactors returned by $\text{GCD}$ are relatively prime. Therefore each gcd calculation satisfies condition (27), and Hensel's construction applies at every stage.
The resulting polynomials $u_1(x),u_2(x),\ldots,u_e(x)$ satisfy
$$ u(x)=u_1(x)u_2(x)^2u_3(x)^3\cdots u_e(x)^e, $$
with each $u_i(x)$ squarefree and pairwise relatively prime. This completes the construction.
This completes the proof.
∎