Randomized polynomial-time root counting in prime power rings
Leann Kopp, Natalie Randall, J. Maurice Rojas, Yuyu Zhu · Mathematics of Computation · 2019
Suppose k , p ∈ N k,p\!\in \!\mathbb {N} with p p prime and f ∈ Z [ x ] f\!\in \!\mathbb {Z}[x] is a univariate polynomial with degree d d and all coefficients having absolute value less than p k p^k . We give a Las Vegas randomized algorithm that computes the number of roots of f f in Z / ( p k ) \mathbb {Z}/\!\left (p^k\right ) within time d 3 ( k log p ) 2 + o ( 1 ) d^3(k\log p)^{2+o(1)} . (We in fact prove a more intricate complexity bound that is slightly better.) The best previous general algorithm had (deterministic) complexity exponential in k k . We also present some experimental data evincing the potential practicality of our algorithm.