Noisy interpolation of sparse polynomials in finite fields

DOI10.1007/s00200-005-0180-1zbMath1131.11077OpenAlexW2032004558MaRDI QIDQ2491980

Arne Winterhof, Igor E. Shparlinski

Publication date: 31 May 2006

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00200-005-0180-1

zbMATH Keywords

exponential sumsfinite fieldssparse polynomials

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Polynomials over finite fields (11T06)

Related Items (4)

A hidden number problem in small subgroups ⋮ Correcting noisy exponentiation black-boxes modulo a prime ⋮ Noisy polynomial interpolation modulo prime powers ⋮ Interpolation and Approximation of Polynomials in Finite Fields over a Short Interval from Noisy Values

Cites Work

• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• The complexity of sparse polynomial interpolation over finite fields
• On the hardness of approximating the permanent of structured matrices
• Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes
• Reconstructing Algebraic Functions from Mixed Data
• Computational Complexity of Sparse Rational Interpolation
• BOUNDS ON EXPONENTIAL SUMS AND THE POLYNOMIAL WARING PROBLEM MOD p
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• List decoding of algebraic-geometric codes
• Sparse polynomial approximation in finite fields
• Randomness efficient identity testing of multivariate polynomials
• A hidden number problem in small subgroups
• Public Key Cryptography – PKC 2004
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Noisy interpolation of sparse polynomials in finite fields