  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}$ (extension fields access is not permitted). The naive
interpolation algorithm needs $O(e\, \mathrm{deg}\, f)$ queries and thus
requires $e\, \mathrm{deg}\, f<q$. We design algorithms that are asymptotically
better in certain cases; requiring only $e^{o(1)}$ queries to the oracle. In
the randomized (and quantum) setting, we give a substantially better
interpolation algorithm, that requires only $O(\mathrm{deg}\, f \log q)$
queries. Such results have been known before only for the special case of a
linear $f$, called the hidden shifted power problem.
  We use techniques from algebra, such as effective versions of Hilbert's
Nullstellensatz, and analytic number theory, such as results on the
distribution of rational functions in subgroups and character sum estimates.
