Is there any algorithm which can find a common divisor of two polynomials modulo $p^k$?

Question

Let us consider two monic polynomials $f(X), g(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]$. Now, we call $h(X)$ is a divisor of $f(X)$, if there exists a $l(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]$ such that $f(X) = h(X) \cdot l(X)$.

Question: Is there any algorithm that does the following:

Input: $f(X), g(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]$, such that both are monic polynomials.

Output:

• Either gives at least one $h(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]$ such that $h(X)$ is a common divisor of $f(X),g(X)$;

• Or gives a certificate of coprimality.

---

$f(X)$ and $g(X)$ can have exponentially many factors. If there are any common factors, then can we find one of them, which I am calling $h(X)$? If there are no common factors, then can we certify that $f(X), g(X)$ are two coprime factors?

---

Observation: One more interesting thing one can notice in this case, that if $f(X), g(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]$ and suppose we know some factorization of both of these polynomials, but surprisingly, we still can't find the common divisors of these two polynomilas.

Example: Let $f(X) = X^2, g(X) = X^2 -5X+6 \in \dfrac{\mathbb{Z}}{9\mathbb{Z}}[X]$. Now, $f(X)$ have $3$ possible factorizations, which are $X^2, (X-3)(X+3), (X-6)(X+6)$ and $g(X)$ can be factored as $(X-3)(X-2)$ in $\bmod{3^2}$. But to get a common factor, you need to know all the factorization of $f(X) \bmod{3^2}$. Like if one finds the factor $f(X) = (X-6)(X+6)$, then it is clearly saying that there are no common factors between $f$ and $g$ by looking at only one possible factor. But actually $(X-3)$ is a common factor of $f,g$ in modulo $3^2$.

---

I also asked this question on MSE.

Answer 1

The following lemma seems helpful in reducing the amount of search needed: Let $h(x)$ be a common divisor of $f$ and $g$ of minimal degree. Let $\widetilde{h}(x)$ be any lift of $h(x)$ to an element of $\mathbb Z_p[x]$. Then $\widetilde{h}(x)$ is irreducible.

The proof is that if $\widetilde{h}$ splits as $\widetilde{h}_1\widetilde{h}_2$ then the reductions of $\widetilde{h}_1$ and $\widetilde{h}_2$ mod $p^k$ both divide $h$ and so divide $f$ and $g$, but have lesser degree.

So we may restrict attention to $h$ such that any lift of $h$ to $\mathbb Z_p[x]$ is irreducible, and use our knowledge of irreducible polynomials in $\mathbb Z_p[x]$.

For one, by Hensel's lemma, such polynomials must reduce mod $p$ to a power of an irreducible polynomial in $\mathbb F_p[x]$. So we can start our search by considering all powers of all irreducible polynomials dividing the gcd of $f$ and $g$ modulo $p$, which is a list of length at most the degree of the gcd of $f$ and $g$ and thus can be efficiently brute-force searched through.

I'm not immediately sure what is a good way to handle the lift from mod $p$ to mod $p^k$, though I can see how to do some special cases.

---

A necessary condition for a solution to exist is that there exists $\alpha \in \overline{\mathbb Z}_p$ (i.e. the integral closure of $\mathbb Z_p$ inside the algebraic closure of $\mathbb Q_p$) such that $f(\alpha)$ and $g(\alpha)$ are both divisible by $p^k$ (here we have lifted $f$ and $g$ arbitrarily to $\mathbb Z_p$). This is necessary since any root of $h$ (lifted arbitrarily to $\mathbb Z_p$) will have this property.

If the minimal polynomial of $\alpha$ is irreducible mod $p$, this condition it is also sufficient, as then for $h$ the minimal polynomial of $\alpha$ we can express the coefficients of $f$ modulo $h$ as $\mathbb Z_p$-linear functions of $f(\alpha)$, and so these are divisible by $p^k$, and the same is true for $g$.

I will give an algorithm (modulo arithmetic in $\overline{\mathbb Q_p}$ that I believe is known how to do efficiently) to decide this necessary condition.

In particular, you raise on MSE the question of when $f$ and $g$ have a common root. This occurs if and only if there exists such an $\alpha$ in \mathbb Z_p$.

To do this, we observe that there exists $\alpha$ such that that $f(\alpha)$ and $g(\alpha)$ are both divisible by $p^k$ if and only if there exists $\alpha$ a root of $f$ or $g$ such that $f(\alpha)$ and $g(\alpha)$ are divisible by $p^k$. Indeed, let $\beta_1,\dots, \beta_n$ be the roots of $f$ and $\beta_{n+1},\dots, \beta_{n+m}$ be the roots of $g$, then $f(\alpha) = \prod_{i=1}^n (\alpha -\beta_i)$. There is some $j$, not necessarily unique, that maximizes the $p$-adic valuation of $\alpha-\beta_j$. For this $j$, the $p$-adic valuation of $\alpha-\beta_i$ is at most the $p$-adic valuation of $\beta_i-\beta_j$, since otherwise $\beta_i-\beta_j$ would be the difference of two terms $\alpha-\beta_j$ and $\alpha-\beta_i$ of greater $p$-adic valuation, contradicting the non-archimedean property of $p$-adic valuation. So the $p$-adic valuation of $f(\alpha)=\prod_{i=1}^n (\alpha -\beta_i)$ is at most the $p$-adic valuation of $\prod_{i=1}^n (\beta_j -\beta_i)=f(\beta_j)$, so if $f(\alpha)$ has $p$-adic valuation at least $k$ then so does $f(\beta_j)$. The same argument works for $g$.

So it suffices to test the roots $\beta_1,\dots,\beta_{n+m}$, and see if they have this property.

For your question about roots in $\mathbb Z_p$, each of the roots $\beta_1,\dots, \beta_{n+m}$ has a closest approximation in $\mathbb Z_p$ (i.e. an element $\alpha$ in $\mathbb Z_p$ that minimizes the $p$-adic valuation of $\alpha-\beta_j$) and it suffices to test these elements. So this can be done without exponential search.