Counting the roots of a polynomial modulo p2
MSRIUP 2017: Solving Systems of Polynomial Equations June 24, 2017  August 06, 2017
Location: SLMath: Baker Board Room
Hammonds, Johnson, Patini
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.
Hammonds, Johnson, Patini
H.264 Video 
Talk_1.mp4

Download 
Please report video problems to itsupport@slmath.org.
See more of our Streaming videos on our main VMath Videos page.