Counting the roots of a polynomial modulo p2

Until recently, the only known method of finding the roots of polynomials over prime power rings, other than fields, was brute force. One reason for this is the lack of a division algorithm, thus obstructing the use of greatest common divisors. Suppose f is any nonzero univariate polynomial of degree d in Z/p^nZ[x]. For the case n=2, we prove a new efficient algorithm to count the roots in Z/p^2Z within time polynomial in d + log p. The key idea is to partition the roots via their image under reduction modulo p, and then carefully use Hensel's Lemma. This builds upon recent work of Cheng, Gao, Rojas, and Wan.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.