  Finding an irreducible factor, of a polynomial $f(x)$ modulo a prime $p$, is
not known to be in deterministic polynomial time. Though there is such a
classical algorithm that {\em counts} the number of irreducible factors of
$f\bmod p$. We can ask the same question modulo prime-powers $p^k$. The
irreducible factors of $f\bmod p^k$ blow up exponentially in number; making it
hard to describe them. Can we count those irreducible factors $\bmod~p^k$ that
remain irreducible mod $p$? These are called {\em basic-irreducible}. A simple
example is in $f=x^2+px \bmod p^2$; it has $p$ many basic-irreducible factors.
Also note that, $x^2+p \bmod p^2$ is irreducible but not basic-irreducible!
  We give an algorithm to count the number of basic-irreducible factors of
$f\bmod p^k$ in deterministic poly(deg$(f),k\log p$)-time. This solves the open
questions posed in (Cheng et al, ANTS'18 \& Kopp et al, Math.Comp.'19). In
particular, we are counting roots $\bmod\ p^k$; which gives the first
deterministic poly-time algorithm to compute Igusa zeta function of $f$. Also,
our algorithm efficiently partitions the set of all basic-irreducible factors
(possibly exponential) into merely deg$(f)$-many disjoint sets, using a compact
tree data structure and {\em split} ideals.
