Using Newton Sums in Small Characteristic
Eric Schost, University of Western Ontario
Friday, September 10, 2004, at U. of Western Ontario.
Abstract:
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.
|