Finding roots of a polynomial f(x_1,...,x_n), in a prime field F_p, is a basic question; with a long history and several practical algorithms known. This question is open when we ask it for roots mod p^k, k >= 2. This is due to the difficulty of lifting singular F_p-roots to Z/<p^k>. Eg. f= x_1^3-px_2^2, or f= x_1^3-p, modulo p^2. Now, it is unclear how to even test the existence of roots; as the only F_p-root here, x_1 = 0 mod p, starts behaving unpredictably when `lifted' mod p^2.

In this work, we give the first algorithm to describe these roots in a practical way. Notably, when n and degree of f are constant, our deterministic algorithm is polynomial-time (in k, p). Our method gives the first efficient algorithms for the following problems ---which were erstwhile open even for n=2--- (1) to represent all (infinitely-many) p-adic roots, and (2) to compute Igusa's local zeta function. In general, ours is a new effective method to prove the rationality of this zeta function.