Sparse Polynomial Interpolation with Finitely Many Values for the Coefficients

04/14/2017

∙

by   Qiao-Long Huang, et al.

∙

0

∙

share

In this paper, we give new sparse interpolation algorithms for black box polynomial f whose coefficients are from a finite set. In the univariate case, we recover f from one evaluation of f(a) for a sufficiently large number a. In the multivariate case, we introduce the modified Kronecker substitution to reduce the interpolation of a multivariate polynomial to the univariate case. Both algorithms have polynomial bit-size complexity.