Polynomial interpolation and identity testing from high powers over finite fields

Gábor Ivanyos, Marek Karpinski, Miklos Santha, Nitin Saxena, Igor E. Shparlinski*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

We consider the problem of recovering (that is, interpolating) and identity testing of a “hidden” monic polynomial ƒ, given an oracle access to ƒ(χ)e for χ ∈ Fq, where Fq is finite field of q elements (extension fields access is not permitted). The naive interpolation algorithm needs O(e deg ƒ) queries and thus requires e deg ƒ < 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 ƒ log q) queries. Such results have been known before only for the special case of a linear ƒ, 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.

Original languageEnglish
Pages (from-to)560-575
Number of pages16
JournalAlgorithmica
Volume80
Issue number2
Early online date5 Jan 2017
DOIs
Publication statusPublished - Feb 2018
Externally publishedYes

Keywords

  • Black-box interpolation
  • Deterministic algorithm
  • Hidden polynomial power
  • Nullstellensatz
  • Quantum algorithm
  • Randomised algorithm
  • Rational function

Fingerprint

Dive into the research topics of 'Polynomial interpolation and identity testing from high powers over finite fields'. Together they form a unique fingerprint.

Cite this