3
$\begingroup$

In How hard is it to compute the number of prime factors of a given integer? a question was asked on computing number of prime factors of an integer.

Suppose we have a polynomial $f(X)\in \Bbb Z[X]$ with leading coefficient $1$ and the constant term $1$, there is a polynomial time algorithm in terms of degree and size of coefficients to factor $f(X)=\prod_if_i(X)$ where each $f_i(X)$ is in $\Bbb Z[X]$.

However if I just want to count the number of irreducible factors of $f(X)$, is there a way to do this in polynomial time without factoring the polynomial?

Probably an algorithm to the question: "Given $F(x)\in\Bbb Z[x]$, find maximum $k$ such that $F(x)=f_1(x)^{a_1}\dots f_k(x)^{a_k}$ where $f_i(x)\in\Bbb Z[x]$ has $deg(f_i(x))\geq 1$ and $i\neq j\implies f_i(x)\neq f_j(x)$ with each $a_i > 0$?" is close to the question here.

Atleast can we say $k>1$ without factoring? Or would this also split the polynomial?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I don’t think there is any coherent way how to define that an algorithm does not factor the polynomial behind the scenes. $\endgroup$
    – Emil Jeřábek
    Nov 28, 2014 at 20:25
  • $\begingroup$ "Given $F(x)\in\Bbb Z[x]$, find max $k$ such that $F(x)=f_1(x)^{a_1}\dots f_k(x)^{a_k}$ where $f_i(x)\in\Bbb Z[x]$ has $deg(f_i(x))\geq 1$ and $i\neq j\implies f_i(x)\neq f_j(x)$ with each $a_i > 0$"? $\endgroup$
    – Turbo
    Nov 28, 2014 at 22:21

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.