Assume the polynomials here are dense.
In here it was asked the difficulty of counting prime factors of an integer.
We know for the cases of primitive polynomials in $\Bbb Z[x]$ and any polynomial in $\Bbb F_q[x]$ counting irreducible factors is easy since for primitive polynomials in $\Bbb Z[x]$ we have deterministic LLL algorithm and for any polynomial in $\Bbb F_q[x]$ we have randomized algorithms.
$1$ My first question is whether it would be possible to have an algorithm to count number of irreducible factors for either the case of primitive polynomials in $\Bbb Z[x]$ or the case of any polynomial in $\Bbb F_q[x]$ in at least randomized polynomial time or even in randomized subexponential time without factoring?
$2$ Given that we know how to test primality without factoring my second question is whether it would be possible to test for irreducibility without factoring polynomials?
Query $2$ is affirmative if we are in $\Bbb F_q[x]$ but unclear for primitive polynomials in $\Bbb Z[x]$.
What is know about these in sparse polynomial case?
