  We consider the problem of recovering a hidden monic polynomial f(X) of
degree d > 0 over the finite field F of p elements given a black box which, for
any x in F, evaluates the quadratic character of f(x). We design a classical
algorithm of complexity O(d^2 p^{d + c}), for any c > 0, and also show that the
quantum query complexity of this problem is O(d). Some of our results extend
those of Wim van Dam, Sean Hallgren and Lawrence Ip obtained in the case of a
linear polynomial f(X) = X + s (with unknown s); some are new even in this
case.
