
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2015  Copyright 2015 Universität Bonn, Institut für Informatik, Abt. V  
85353 23.02.2015 
Polynomial Interpolation and Identity Testing from High Powers over Finite Fields
Gabor Ivanyos, Marek Karpinski, Miklos Santha, Nitin Saxena and Igor E. Shparlinski [Download PostScript] [Download PDF]
We consider the problem of recovering (i.e. interpolating) and identity testing of a “hidden” monic polynomial f, given an oracle access to f(x)^{e} for x ∈ F_{q} (extension fields access is not permitted). The naive interpolation algorithm needs O(e deg f ) queries and thus requires e deg f < q. We design algorithms that are asymptotically better in certain cases; requiring only e^{o(1)} queries to the oracle. In the randomized (and quantum) setting, we give a substantially better interpolation algorithm, that requires only O(deg f log q) queries. Such results have been known before only for the special case of a linear f, called the hidden shifted power problem. 

Last Change:
02/23/15 at 08:57:27
English 
Universität Bonn > Institut für Informatik > Abteilung V 