Mathematical Sciences Research Institute

Home » MSRI-UP » Schedules » Counting the roots of a polynomial modulo p2

Counting the roots of a polynomial modulo p2

MSRI-UP 2017: Solving Systems of Polynomial Equations June 24, 2017 - August 06, 2017

August 04, 2017 (09:15 AM PDT - 09:50 AM PDT)
Speaker(s): Trajan Hammonds (Carnegie Mellon University), Jeremy Johnson (Humboldt State University), Angela Patini (University of Pennsylvania)
Location: MSRI: 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.

Supplements No Notes/Supplements Uploaded
Video/Audio Files

Hammonds, Johnson, Patini

H.264 Video Talk_1.mp4 965 MB video/mp4 rtsp://videos.msri.org/data/000/029/314/original/Talk_1.mp4 Download
Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included). Please Click Here to send an email to MSRI to purchase the DVD.

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