Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2015 Copyright 2015 Universität Bonn, Institut für Informatik, Abt. V


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 ∈ Fq (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 eo(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.
We use techniques from algebra, such as effective versions of Hilbert’s Nullstellensatz, and analytic number theory, such as results on the distribution of rational functions in subgroups and character sum estimates.

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

Powered by Zope