@inproceedings{BoGoPeSc05,
author = {Bostan, A. and Gonz{\'a}lez-Vega, L. and Perdry, H. and
Schost, {\'E}.},
title = {From {N}ewton sums to coefficients: complexity issues in
characteristic $p$},
booktitle = {MEGA'05},
year = {2005},
note = {Eighth International Symposium on Effective Methods in
Algebraic Geometry, Porto Conte, Alghero, Sardinia (Italy), May 27th -- June
1st},
abstract = {We consider the following problem: given the first $d$
Newton sums of a degree $d$ polynomial $P$, recover the coefficients of $P$.
We propose fast algorithms to perform this conversion for polynomials over
the $p$-adic ring $\Z_p$. As an application, we deduce a new algorithm to
compute the \emph{composed product} of polynomials over the finite field
$\F_p$, whose bit-complexity improves the known results by a factor of
$\,\log d$ in many cases.},
}