Sparse Polynomial Interpolation with Finitely Many Values for the Coefficients

Qiao-Long Huang, Xiao-Shan Gao

Abstract

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 $$f(\beta )$$ for a sufficiently large number $$\beta $$ . In the multivariate case, we introduce the modified Kronecker substitution to reduce the interpolation of a multivariate polynomial to that of the univariate case. Both algorithms have polynomial bit-size complexity.
BibTeX
@inproceedings{huang2017sparse,
  author = {Qiao-Long Huang and Xiao-Shan Gao},
  title = {{Sparse Polynomial Interpolation with Finitely Many Values for the Coefficients}},
  booktitle = {CASC},
  year = {2017},
  doi = {10.1007/978-3-319-66320-3\_15},
}

Loading related content...

Figure