Polynomial interpolation and identity testing from high powers over finite fields

DOI10.1007/S00453-016-0273-1zbMATH Open1390.11128arXiv1502.06631OpenAlexW2964208696MaRDI QIDQ1709581FDOQ1709581

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

Publication date: 6 April 2018

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Title not available (Why is that?)
• Factorization in generalized arithmetic progressions and application to the Erdős-Szemerédi sum-product problems
• Sharp estimates for the arithmetic Nullstellensatz
• Heights of varieties in multiprojective spaces and arithmetic nullstellensätze
• Title not available (Why is that?)
• On the Hidden Shifted Power Problem
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Product Sets of Rationals, Multiplicative Translates of Subgroups in Residue Rings, and Fixed Points of the Discrete Logarithm
• Modern computer algebra
• Arithmetic Circuits: A survey of recent results and open questions
• Quantum algorithms for weighing matrices and quadratic residues
• Concentration of points on curves in finite fields
• Quantum Algorithms for Some Hidden Shift Problems
• Progress on polynomial identity testing
• Polynomial values in small subgroups of finite fields
• Title not available (Why is that?)
• Algorithms for Black-Box Fields and their Application to Cryptography
• Classical and quantum function reconstruction via character evaluation
• Subgroups generated by rational functions in finite fields
• Products with variables from low-dimensional affine spaces and shifted power identity testing in finite fields

Cited In (6)

• 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
• Additive energy of polynomial images
• 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)