Polynomial Interpolation and Identity Testing from High Powers over Finite Fields

Gabor Ivanyos, Marek Karpinski, Miklos Santha +2

We consider the problem of recovering (that is, interpolating) and identity testing of a "hidden" monic polynomial $f$, given an oracle access to $f(x{)}^e$ for $x\in {\mathbb{F}}_q$ (…