Revisit sparse polynomial interpolation based on randomized Kronecker substitution

DOI10.1007/978-3-030-26831-2_15MaRDI QIDQ2175579zbMATH OpenOpenAlexFDO

Authors Qiao-Long Huang, Xiao-Shan Gao

Publication date 29 April 2020

Full work available at URL https://arxiv.org/abs/1712.05481

zbMATH Keywords

black-box methodMonte Carlo algorithmrandomized Kronecker substitutionsparse polynomial interpolation

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical interpolation (65D05) Symbolic computation and algebraic computation (68W30)

Abstract: In this paper, a new reduction based interpolation algorithm for black-box multivariate polynomials over finite fields is given. The method is based on two main ingredients. A new Monte Carlo method is given to reduce black-box multivariate polynomial interpolation to black-box univariate polynomial interpolation over any ring. The reduction algorithm leads to multivariate interpolation algorithms with better or the same complexities most cases when combining with various univariate interpolation algorithms. We also propose a modified univariate Ben-or and Tiwarri algorithm over the finite field, which has better total complexity than the Lagrange interpolation algorithm. Combining our reduction method and the modified univariate Ben-or and Tiwarri algorithm, we give a Monte Carlo multivariate interpolation algorithm, which has better total complexity in most cases for sparse interpolation of black-box polynomial over finite fields.

Recommendations

• Multivariate sparse interpolation using randomized Kronecker substitutions
• Deterministic sparse interpolation of black-box multivariate polynomials using Kronecker type substitutions
• Sparse polynomial interpolation with finitely many values for the coefficients
• Sparse polynomial interpolation based on diversification
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields

Cited in

(11)

• Sparse polynomial interpolation based on diversification
• Sparse polynomial interpolation based on derivatives
• Study and improvement of the multiplicative noisy polynomial interpolation algorithm on integral ring
• Multivariate sparse interpolation using randomized Kronecker substitutions
• Deterministic sparse interpolation of black-box multivariate polynomials using Kronecker type substitutions
• Randomized interpolation and approximation of sparse polynomials stPreliminary version
• Diversification improves interpolation
• Symbolic-numeric sparse interpolation of multivariate polynomials
• How to compress encrypted data
• Fast interpolation and multiplication of unbalanced polynomials
• A new sparse polynomial GCD by separating terms

This page was built for publication: Revisit sparse polynomial interpolation based on randomized Kronecker substitution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2175579)