Fast interpolation and multiplication of unbalanced polynomials - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2024

Fast interpolation and multiplication of unbalanced polynomials

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

Abstract

We consider the classical problems of interpolating a polynomial given a black box for evaluation, and of multiplying two polynomials, in the setting where the bit-lengths of the coefficients may vary widely, so-called unbalanced polynomials. Let f ∈ Z[x] be an unknown polynomial and s, D be bounds on its total bit-length and degree, our new interpolation algorithm returns f with high probability using Õ(s log D) bit operations and O(s log D log s) black box evaluation. For polynomial multiplication, assuming the bit-length s of the product is not given, our algorithm has an expected running time of Õ(s log D), whereas previous methods for (resp.) dense or sparse arithmetic have at least Õ(sD) or Õ s 2 bit complexity.
Fichier principal
Vignette du fichier
report.pdf (415.14 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Licence

Dates and versions

lirmm-04746015 , version 1 (21-10-2024)

Licence

Identifiers

Cite

Pascal Giorgi, Bruno Grenet, Armelle Perret Du Cray, Daniel S Roche. Fast interpolation and multiplication of unbalanced polynomials. ISSAC 2024 - International Symposium on Symbolic and Algebraic Computation, Jul 2024, Raleigh (North Carolina), United States. pp.437-446, ⟨10.1145/3666000.3669717⟩. ⟨lirmm-04746015⟩
9 View
2 Download

Altmetric

Share

More