Classical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation

Details Classical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation Classical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation

2002-12-02

arxiv.org/abs/quant-ph/0212016v1

Physics

Quantum Physics

14 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Classical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Classical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Classical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-496460