Interpolation and Approximation of Polynomials in Finite Fields over a Short Interval from Noisy Values

DOI10.1080/10586458.2014.890918zbMath1310.11117arXiv1401.1331OpenAlexW2963374191MaRDI QIDQ5249301

Ronald Rietman, L. M. G. M. Tolhuizen, Oscar Garcia-Morchon, Igor E. Shparlinski

Publication date: 30 April 2015

Published in: Experimental Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

finite fieldslattice reductionnoisy polynomial interpolation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16)

Related Items

Additive energy and a large sieve inequality for sparse sequences, Noisy polynomial interpolation modulo prime powers, Close values of shifted modular inversions and the decisional modular inversion hidden number problem

Cites Work

• Unnamed Item
• Unnamed Item
• Vinogradov's mean value theorem via efficient congruencing
• Factoring polynomials with rational coefficients
• On a problem of Erdős involving the largest prime factor of \(n\)
• On the concentration of points of polynomial maps and applications
• Vinogradov's mean value theorem via efficient congruencing. II
• Noisy interpolation of sparse polynomials in finite fields
• A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
• SOLUTIONS TO POLYNOMIAL CONGRUENCES IN WELL-SHAPED SETS
• Multigrade efficient congruencing and Vinogradov's mean value theorem
• Solving Hidden Number Problem with One Bit Oracle and Advice
• BOUNDS ON EXPONENTIAL SUMS AND THE POLYNOMIAL WARING PROBLEM MOD p