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

Abstract

[summary] We consider a modification of the noisy polynomial interpolation problem of recovering an unknown polynomial from approximate values of the residues of f(t) modulo a prime p at polynomially many points t taken from a short interval.

2000 AMS Subject Classification::

• 11T71
• 11Y16
• 68Q25
• 68W30

Keywords::

• noisy polynomial interpolation
• finite fields
• lattice reduction