A probabilistic algorithm for verifying polynomial middle product in linear time

Pascal Giorgi 1
1 ECO - Exact Computing
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01538453
Contributeur : Pascal Giorgi <>
Soumis le : jeudi 13 septembre 2018 - 15:32:34
Dernière modification le : mercredi 19 septembre 2018 - 01:14:32

Fichier

giorgi-certification-midp.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pascal Giorgi. A probabilistic algorithm for verifying polynomial middle product in linear time. Information Processing Letters, Elsevier, 2018, 139, pp.30-34. 〈10.1016/j.ipl.2018.06.014〉. 〈lirmm-01538453v2〉

Partager

Métriques

Consultations de la notice

26

Téléchargements de fichiers

22