Classical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation

Alexander Russell, Igor Shparlinski

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 qu…