Symbolic Computation Group

David R. Cheriton School of Computer Science
University of Waterloo, Waterloo, Ontario, Canada

Using Newton Sums in Small Characteristic
Eric Schost, University of Western Ontario
Friday, September 10, 2004, at U. of Western Ontario.


Let us consider the following problem: given the first d Newton sums of a degree d polynomial P, recover the coefficients of P.

If the coefficients of P lie in a field of characteristic zero, we have many solutions at our disposal: unrolling the Newton relations gives an algorithm of complexity O(d^2), whereas using fast exponentiation algorithms, the complexity drops to O(d), up to linear factors.

If the base field has (small) positive characteristic, things get more complicated, since all these algorithms require divisions by 2,3,... If the base field is F_p=Z/pZ, we will see however that computations in rings of the form Z/p^NZ can help us solve our problem.

I will show that a (surprisingly) moderate value of N is actually enough to get the expected results. As an application, I will give a new algorithm to compute the composed product of polynomials over F_p, whose bit-complexity improves the known results by a factor of log(d) in many cases.

This is a joint work with Alin Bostan, Laureano Gonzalez Vega and Herve Perdry.


Last modified on Sunday, 04 November 2012, at 15:42 hours.