Sparse polynomial interpolation based on diversification

DOI10.1007/S11425-020-1791-5MaRDI QIDQ2143469zbMATH OpenOpenAlexFDO

Authors Qiao-Long Huang

Publication date 31 May 2022

Published in Science China. Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

interpolationfinite fielddiversification

Mathematics Subject Classification ID

Moment problems and interpolation problems in the complex plane (30E05) Interpolation in approximation theory (41A05) Linear operator methods in interpolation, moment and extension problems (47A57) Holomorphic, polynomial and rational approximation, and interpolation in several complex variables; Runge pairs (32E30)

Abstract: We consider the problem of interpolating a sparse multivariate polynomial over a finite field, represented with a black box. Building on the algorithm of Ben-Or and Tiwari for interpolating polynomials over rings with characteristic zero, we develop a new Monte Carlo algorithm over the finite field by doing additional probes. To interpolate a polynomial $fin{F}_q[x_1,dots,x_n]$ with a partial degree bound $D$ and a term bound $T$, our new algorithm costs $O^{h}icksim(nTlo{g}^{2}q+nTsqrtDlogq)$ bit operations and uses $2(n+1)T$ probes to the black box. If $qgeqO(n{T}^{2}D)$, it has constant success rate to return the correct polynomial. Compared with previous algorithms over general finite field, our algorithm has better complexity in the parameters $n,T,D$ and is the first one to achieve the complexity of fractional power about $D$, while keeping linear in $n,T$. A key technique is a randomization which makes all coefficients of the unknown polynomial distinguishable, producing a diverse polynomial. This approach, called diversification, was proposed by Giesbrecht and Roche in 2011. Our algorithm interpolates each variable independently using $O(T)$ probes, and then uses the diversification to correlate terms in different images. At last, we get the exponents by solving the discrete logarithms and obtain coefficients by solving a linear system. We have implemented our algorithm in Maple. Experimental results shows that our algorithm can applied to sparse polynomials with large degree. We also analyze the success rate of the algorithm.

Recommendations

• Diversification improves interpolation
• Sparse interpolation over finite fields via low-order roots of unity
• Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications
• A new algorithm for sparse interpolation of multivariate polynomials
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields

Cites work

• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 1254255 (Why is no real title available?)
• scientific article; zbMATH DE number 1262424 (Why is no real title available?)
• A sparse modular GCD algorithm for polynomials over algebraic function fields
• Algorithms for the non-monic case of the sparse modular GCD algorithm
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Diversification improves interpolation
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Interpolating polynomials from their values
• Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications
• Modern computer algebra
• Monte Carlo Methods for Index Computation (mod p)
• Multivariate sparse interpolation using randomized Kronecker substitutions
• Randomness efficient identity testing of multivariate polynomials
• Revisit sparse polynomial interpolation based on randomized Kronecker substitution

Cited in

(14)

• Diversification improves interpolation
• A local decision test for sparse polynomials
• Randomized interpolation and approximation of sparse polynomials stPreliminary version
• A sparse polynomial interpolation based on racing strategy
• Polynomial homotopy method for the sparse interpolation problem. I: Equally spaced sampling
• Revisit sparse polynomial interpolation based on randomized Kronecker substitution
• Fast interpolation and multiplication of unbalanced polynomials
• Early termination in sparse interpolation algorithms
• Sparse interpolation over finite fields via low-order roots of unity
• The interpolation problem for \(k\)-sparse polynomials and character sums
• Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications
• Bit complexity of polynomial GCD on sparse representation
• Robust algorithms for sparse interpolation of multivariate polynomials
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields

Describes a project that uses

Uses Software

• Maple
• FOXBOX

This page was built for publication: Sparse polynomial interpolation based on diversification

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