I have implemented Berlekamp-Hensel algorithm that provide to factor (into terms of irreducible polynomials) primitive and square-free polynomial over $\mathbb{Z}$. At first, this algorithm obtains irreducible factorization of $f(x)$ over $\mathbb{Z}_p$ (using Berlekamp algorithm) and then uses Hensel Lifting process to obtain factorization over $\mathbb{Z}$. But, now I want to extend this algorithm to factor polynomials over field $\mathbb{Q}$. I try to use following idea:
- For any polynomial $u(x)=u_0+u_1x+u_2x^2+...+u_nx^n \in \mathbb{Q}[x]$, where $u_i=\frac{a_i}{b_i}\in \mathbb{Q}$ we can define $\operatorname{LCM}(b_0,...,b_1)=M$
- So, we can consider the polynomial $v(x)=Mu(x) \in \mathbb{Z}[x]$
- Then, $u(x)=\frac{v(x)}{M}=\frac{1}{M}\operatorname{content}(v(x))\operatorname{primitivepart}(v(x))$
- And then we need to factor $\operatorname{primitivepart}(v(x))$ over $\mathbb{Z}$
Since Berlekamp-Hensel algorithm works with the primitive and square-free polynomial, we need obtain square-free polynomial. Therefore, my question is: at what step should I apply square-free factorization algorithm ? For the most initial polynomial $u(x) \in \mathbb{Q}[x]$ or for the corresponding primitive polynomial $\operatorname{primitivepart}(v(x)) \in \mathbb{Z}[x]$ ? And I know that there are separate square-free algorithms for the $\mathbb{Q}[x]$ and for the $\mathbb{Z}[x]$. So, which one should I use ?