Fast interpolation and multiplication of unbalanced polynomials - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2024

Fast interpolation and multiplication of unbalanced polynomials

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

Résumé

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
Origine Fichiers produits par l'(les) auteur(s)
Licence

Dates et versions

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

Licence

Identifiants

Citer

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 Consultations
2 Téléchargements

Altmetric

Partager

More