Abstract: This paper analyses a multiplicative noisy polynomial interpolation algorithm in the finite field presented by J. von zur Gathen and I. E. Shparlinski and presents an amended algorithm. By the lattice reduction algorithm on the nearest vector presented by L.Babai, a more accurate estimate vector can be obtained and the coefficients of the multiple polynomial of the interpolation polynomial can be computed. Then the coefficients of the original interpolation polynomial can be computed. The amended algorithm reduces the lower bound of the order of the finite field and can apply to the polynomials in the finite field whose order is lower.

Key words: polynomial interpolation, modular multiplicatively approximate black box(MMABB), lattice reduction