Roots of univariate polynomials modulo prime powersSpeaker: Ashish Dwivedi
Title: Roots of univariate polynomials modulo prime powers
Date: 22 Jul 2019 5:30pm-7:00pm
Location: Maxwell-Dworkin 323
Audience background: Chinese remainder theorem, basic of discrete math
Abstract: In this talk, I will talk about how to find and count roots of a given integral univariate polynomial f(x) modulo a prime power p^k. This problem is a natural generalization of a very well studied computational problem- finding roots of a univariate modulo p (or over prime fields). I will start with some examples to understand the difficulty of the problem and then present a randomized algorithm of Berthomieu, Lecerf and Quintin 2013 for root finding. Then I will present recent derandomization result of D., Mittal and Saxena [CCC 2019] to count roots of f(x) mod p^k.