Counting basic-irreducible factors mod p k in deterministic poly-time and p -adic applications

摘要

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 mod p . We can ask the same question modulo prime-powers p k . The irreducible factors of f mod p k blow up exponentially in number; making it hard to describe them. Can we count those irreducible factors mod p k that remain irreducible mod p ? These are called {em basic-irreducible}. A simple example is in f = x 2 + p x mod p 2 ; it has p many basic-irreducible factors. Also note that, x 2 + p mod p 2 is irreducible but not basic-irreducible!We give an algorithm to count the number of basic-irreducible factors of f mod 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 mod 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.