Sparse Polynomial Interpolation and Division in Soft-linear Time - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2022

Sparse Polynomial Interpolation and Division in Soft-linear Time

Pascal Giorgi
Bruno Grenet
Armelle Perret Du Cray
  • Function : Author
  • PersonId : 1064718
  • IdRef : 272431613
Daniel S. Roche

Abstract

Given a way to evaluate an unknown polynomial with integer coefficients, we present new algorithms to recover its nonzero coefficients and corresponding exponents. As an application, we adapt this interpolation algorithm to the problem of computing the exact quotient of two given polynomials. These methods are efficient in terms of the bit-length of the sparse representation, that is, the number of nonzero terms, the size of coefficients, the number of variables, and the logarithm of the degree. At the core of our results is a new Monte Carlo randomized algorithm to recover a polynomial $f(x)$ with integer coefficients given a way to evaluate $f(\theta) \bmod m$ for any chosen integers $\theta$ and $m$. This algorithm has nearly-optimal bit complexity, meaning that the total bit-length of the probes, as well as the computational running time, is softly linear (ignoring logarithmic factors) in the bit-length of the resulting sparse polynomial. To our knowledge, this is the first sparse interpolation algorithm with soft-linear bit complexity in the total output size. For polynomials with integer coefficients, the best previously known results have at least a cubic dependency on the bit-length of the exponents.
Fichier principal
Vignette du fichier
2202.08106.pdf (321.76 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-03784815 , version 1 (17-10-2023)

Identifiers

Cite

Pascal Giorgi, Bruno Grenet, Armelle Perret Du Cray, Daniel S. Roche. Sparse Polynomial Interpolation and Division in Soft-linear Time. ISSAC 2022 - 47th International Symposium on Symbolic and Algebraic Computation, Jul 2022, Lille, France. pp.459-468, ⟨10.1145/3476446.3536173⟩. ⟨lirmm-03784815⟩
24 View
13 Download

Altmetric

Share

Gmail Facebook X LinkedIn More