A probabilistic algorithm for verifying polynomial middle product in linear time - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Information Processing Letters Year : 2018

A probabilistic algorithm for verifying polynomial middle product in linear time

Pascal Giorgi

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.
Fichier principal
Vignette du fichier
giorgi-certification-midp.pdf (288.63 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
253 View
529 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More