Noisy polynomial interpolation modulo prime powers
share
We consider the noisy polynomial interpolation problem of recovering an unknown s-sparse polynomial f(X) over the ring ℤ_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) ∈ℤ_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 polynomials time algorithm, which for almost given more than a half bits of f(t) for sufficiently many randomly chosen points t ∈ℤ_p^k^*, recovers f(X).
READ FULL TEXT