This exercise discusses a small primes modular algorithm for computing the
squarefree decomposition of a primitive polynomial \(f \in \mathbb{Z}[x]\).
(i) Let \(R\) be a UFD and \(f \in R[x]\) nonconstant and primitive. Prove that
there exist primitive squarefree and pairwise coprime polynomials \(g_{1},
\ldots, g_{m} \in R[x]\) such that \(g_{m}\) is nonconstant and \(f=g_{1}
g_{2}^{2} \cdots g_{m}^{m}\). Show that \(m\) is unique and the \(g_{i}\) are
unique up to multiplication by units in \(R^{\times}\).
For the special cases \(R=\mathbb{Z}\) or \(R=F[y]\), where \(F\) is a field, we can
make the decomposition above unique by stipulating that
\(\operatorname{lc}\left(g_{i}\right) \in R\) be positive or monic,
respectively, assuming that \(l c(f)\) is also positive or monic. Then we call
the sequence \(\left(g_{1}, \ldots, g_{m}\right)\) the primitive squarefree
decomposition of \(f\).
(ii) Now let \(R=\mathbb{Z}, p\) be a prime not dividing \(\operatorname{lc}(f)\)
and \(f \equiv \operatorname{lc}(f) h_{1} h_{2}^{2} \cdots h_{k}^{k}\) mod \(p\)
be the squarefree decomposition of \(f\) modulo \(p\), with monic \(h_{1}, \ldots,
h_{k} \in \mathbb{Z}[x]\) that are squarefree and pairwise coprime modulo \(p\),
and \(h_{k} \neq 1\). Show that \(k \geq m\) and the modular squarefree part
\(h_{1} \cdots h_{k}\) divides modulo \(p\) the squarefree part \(g=g_{1} \cdots
g_{m}\) of \(f\). Prove that \(k=m\) and \(g_{i} \equiv
\operatorname{lc}\left(g_{i}\right) h_{i}\) mod \(p\) for all \(i\) if \(p\) does not
divide the (nonzero) discriminant res \(\left(g, g^{r}\right) \in \mathbb{Z}\)
of \(g\).
(iii) Prove the following generalization of Mignotte's bound (Corollary 6.33):
If \(f, g_{1}, \ldots, g_{m} \in\) \(\mathbb{Z}[x]\) are nonzero polynomials with
\(f=g_{1} \cdots g_{m}\) and \(n=\operatorname{deg} f\), then
$$
\prod_{1 \leq i \leq m}\left\|g_{i}\right\|_{1} \leq(n+1)^{1 / 2}
2^{n}\|f\|_{\infty}
$$
(iv) Design a small primes modular algorithm for computing the primitive
squarefree decomposition of \(f\), in analogy to the small primes modular ged
algorithm \(6.38\). Your algorithm should check that the result is correct, so
that it is Las Vegas, and use \(O^{\sim}\left(n^{2}+n \log A\right)\) word
operations if \(A=\|f\|_{\infty}\).
