Noisy polynomial interpolation modulo prime powers

2020/06/10 by Karpinski, Marek, Shparlinski, Igor
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2006.05685

Abstract

We consider the \it noisy polynomial interpolation problem\/ of recovering an unknown s-sparse polynomial f(X) over the ring \mathbb Z_p^k of residues modulo p^k, where p is a small prime and k is a large integer parameter, from approximate values of the residues of f(t) ∈ \mathbb Z_p^k. Similar results are known for residues modulo a large prime p, however the case of prime power modulus p^k, with small p and large k, is new and requires different techniques. We give a deterministic polynomial time algorithm, which for almost given more than a half bits of f(t) for sufficiently many randomly chosen points t ∈ \mathbb Z_p^k^*, recovers f(X).

Related

• Interpolation and Approximation of Polynomials in Finite Fields over a Short Interval from Noisy Values
• Newton-Hensel Interpolation Lifting
• Sparse interpolation over finite fields via low-order roots of unity
• Randomized Polynomial-Time Root Counting in Prime Power Rings
• Parallel sparse interpolation using small primes