Polynomial interpolation and identity testing from high powers over finite fields

DOI10.1007/S00453-016-0273-1MaRDI QIDQ1709581zbMATH OpenOpenAlexFDO

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

Publication date 6 April 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.06631

zbMATH Keywords

quantum algorithmdeterministic algorithmrational functionrandomised algorithmblack-box interpolationhidden polynomial powernullstellensatz

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quantum algorithms and complexity in the theory of computing (68Q12) Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16)

Abstract: We consider the problem of recovering (that is, interpolating) and identity testing of a "hidden" monic polynomial $f$, given an oracle access to $f(x{)}^e$ for $xinmathbb{F}_q$ (extension fields access is not permitted). The naive interpolation algorithm needs $O(e,mathrmdeg,f)$ queries and thus requires $e,mathrmdeg,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(mathrmdeg,flogq)$ 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.

Recommendations

• Identity testing and interpolation from high powers of polynomials of large degree over finite fields
• On the hidden shifted power problem
• Noisy interpolation of sparse polynomials in finite fields
• Values of rational functions in small subgroups of finite fields and the identity testing problem from powers
• The complexity of sparse polynomial interpolation over finite fields

Cites work

• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1259076 (Why is no real title available?)
• scientific article; zbMATH DE number 954401 (Why is no real title available?)
• scientific article; zbMATH DE number 2121181 (Why is no real title available?)
• Algorithms for black-box fields and their application to cryptography
• Arithmetic circuits: a survey of recent results and open questions
• Classical and quantum function reconstruction via character evaluation
• Concentration of points on curves in finite fields
• Factorization in generalized arithmetic progressions and application to the Erdős-Szemerédi sum-product problems
• Heights of varieties in multiprojective spaces and arithmetic nullstellensätze
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Modern computer algebra
• On the hidden shifted power problem
• Polynomial values in small subgroups of finite fields
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Product Sets of Rationals, Multiplicative Translates of Subgroups in Residue Rings, and Fixed Points of the Discrete Logarithm
• Products with variables from low-dimensional affine spaces and shifted power identity testing in finite fields
• Progress on polynomial identity testing
• Quantum Algorithms for Some Hidden Shift Problems
• Quantum algorithms for weighing matrices and quadratic residues
• Sharp estimates for the arithmetic Nullstellensatz
• Subgroups generated by rational functions in finite fields

Cited in

(8)

• Values of rational functions in small subgroups of finite fields and the identity testing problem from powers
• Query-Efficient Algorithms for Polynomial Interpolation over Composites
• Products with variables from low-dimensional affine spaces and shifted power identity testing in finite fields
• Additive energy of polynomial images
• On the hidden shifted power problem
• Identity testing and interpolation from high powers of polynomials of large degree over finite fields
• Smoothness testing of polynomials over finite fields
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: Polynomial interpolation and identity testing from high powers over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1709581)