2002/12/02 by Alexander Russell, Russell, Alexander, Igor E. Shparlinski +2
Computer Science · Physics and Astronomy · #Coding theory and cryptography #FOS: Physical sciences #Polynomial and algebraic computation #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0212016
14 pages
arxiv created 2002/12/02 · openalex publication_date 2002/12/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(d2 pd + 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.