Randomized Polynomial-Time Root Counting in Prime Power Rings

08/30/2018
by   Leann Kopp, et al.
0

Suppose k,p∈N with p prime and f∈Z[x] is a univariate polynomial with degree d and all coefficients having absolute value less than p^k. We give a Las Vegas randomized algorithm that computes the number of roots of f in Z/(p^k) within time d^3(k 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. We also present some experimental data evincing the potential practicality of our algorithm.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset