Identity Testing and Interpolation from High Powers of Polynomials of Large Degree over Finite Fields
Preprint
Abstract
We consider the problem of identity testing and recovering (that is, interpolating) of a "hidden" monic polynomials $f$, given an oracle access to $f(x)^e$ for $x\in\mathbb F_q$, where $\mathbb F_q$ is the finite field of $q$ elements and an extension fields access is not permitted. The naive interpolation algorithm needs $de+1$ queries, where $d =\max\{{\rm deg}\ f, {\rm deg }\ g\}$ and thus requires $ de<q$. For a prime $q = p$, we design an algorithm that is asymptotically better in certain cases, especially when $d$ is large. The algorithm is based on a result of independent interest in spirit of additive combinatorics. It gives an upper bound on the number of values of a rational function of large degree, evaluated on a short sequence of consecutive integers, that belong to a small subgroup of $\mathbb F_p^*$.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Polynomial values in affine subspaces of finite fieldsJournal d'Analyse Mathématique, 2019
- Polynomial Interpolation and Identity Testing from High Powers Over Finite FieldsAlgorithmica, 2017
- Subgroups generated by rational functions in finite fieldsMonatshefte für Mathematik, 2014
- Products with variables from low-dimensional affine spaces and shifted power identity testing in finite fieldsJournal of Symbolic Computation, 2014
- Modern Computer Algebra2013
- On additive shifts of multiplicative subgroupsSbornik: Mathematics, 2012
- On the Hidden Shifted Power ProblemSIAM Journal on Computing, 2012
- On the concentration of points of polynomial maps and applicationsMathematische Zeitschrift, 2011
- Quantum Algorithms for Some Hidden Shift ProblemsSIAM Journal on Computing, 2006
- Classical and quantum function reconstruction via character evaluationJournal of Complexity, 2004