A probabilistic algorithm for verifying polynomial middle product in linear time - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Information Processing Letters Année : 2018

A probabilistic algorithm for verifying polynomial middle product in linear time

Pascal Giorgi

Résumé

Polynomial multiplication and its variants are a key ingredient in effective computer algebra. While verifying a polynomial product is a well known task, it was not yet clear how to do a similar approach for its middle product variant. In this short note, we present a new algorithm that provides such a verification with the same complexity and probability that for the classical polynomial multiplication. Furthermore, we extend our algorithm to verify any operations that compute only a certain chunk of the product, which is the case for instance of the well known short product operation.
Fichier principal
Vignette du fichier
giorgi-certification-midp.pdf (288.63 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01538453 , version 1 (13-06-2017)
lirmm-01538453 , version 2 (13-09-2018)

Identifiants

Citer

Pascal Giorgi. A probabilistic algorithm for verifying polynomial middle product in linear time. Information Processing Letters, 2018, 139, pp.30-34. ⟨10.1016/j.ipl.2018.06.014⟩. ⟨lirmm-01538453v2⟩
282 Consultations
570 Téléchargements

Altmetric

Partager

More