2015/02/23 by Gábor Ivanyos, Marek Karpiński, Ivanyos, Gabor +7 · 1 citation
Computer Science · #Cryptography and Data Security #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.1502.06631
openalex publication_date 2015/02/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We consider the problem of recovering (that is, interpolating) and identity\ntesting of a "hidden" monic polynomial f, given an oracle access to f(x)e\nfor x\∈ mathbb Fq (extension fields access is not permitted). The naive\ninterpolation algorithm needs O(e , deg , f) queries and thus\nrequires e , deg , f<q. We design algorithms that are asymptotically\nbetter in certain cases; requiring only eo(1) queries to the oracle. In\nthe randomized (and quantum) setting, we give a substantially better\ninterpolation algorithm, that requires only O(deg , f \log q)\nqueries. Such results have been known before only for the special case of a\nlinear f, called the hidden shifted power problem.\n We use techniques from algebra, such as effective versions of Hilbert's\nNullstellensatz, and analytic number theory, such as results on the\ndistribution of rational functions in subgroups and character sum estimates.\n