Home /  MsriUp /  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 (California State Polytechnic University, Humboldt), Angela Patini (University of Pennsylvania)
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.

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
Troubles with video?

Please report video problems to itsupport@slmath.org.

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