Sparse polynomial interpolation based on derivatives
Sparse polynomial interpolation based on derivatives
复制标题
DOI：
10.1016/j.jsc.2022.06.002
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Qiao-Long Huang
中科院分区：
文献类型：
--
作者：
Qiao-Long Huang
We propose two new interpolation algorithms for sparse multivariate polynomials represented by a straight-line program (SLP). Both of our algorithms work over any finite fields F q with large characteristic. The first algorithm is randomized of the Monte Carlo type. Its bit complexity is linear in the number of non-zero terms T and the number of variables n of f . Let D be the partial degree bound of f . If q is in O ( ( n T D ) ( 1 ) ) , our algorithm has better complexity than other existing algorithms. The second algorithm is deterministic; it has better complexity than any existing deterministic algorithms in the field with large characteristic. Its bit complexity is quadratic in n , T , log D .
