Certification of Polynomial Middle Product

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 certifying 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 certification with the same complexity and probability that polynomial multiplication certification. Furthermore, we extend our algorithm to certify any operations that compute only a certain chunk of the product.
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01538453
Contributeur : Pascal Giorgi <>
Soumis le : mardi 13 juin 2017 - 15:53:57
Dernière modification le : jeudi 11 janvier 2018 - 06:27:05
Document(s) archivé(s) le : mardi 12 décembre 2017 - 12:42:42

Fichier

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

Identifiants

  • HAL Id : lirmm-01538453, version 1

Collections

Citation

Pascal Giorgi. Certification of Polynomial Middle Product. 2017. 〈lirmm-01538453〉

Partager

Métriques

Consultations de la notice

80

Téléchargements de fichiers

61