arXiv Open Access 2017

Sparse Polynomial Interpolation with Finitely Many Values for the Coefficients

Qiao-Long Huang Xiao-Shan Gao

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.SC

Penulis (2)

Qiao-Long Huang

Xiao-Shan Gao

Format Sitasi

APA MLA BibTeX

Huang, Q., Gao, X. (2017). Sparse Polynomial Interpolation with Finitely Many Values for the Coefficients. https://arxiv.org/abs/1704.04359

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2017
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓