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.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01538453
Contributor : Pascal Giorgi <>
Submitted on : Thursday, September 13, 2018 - 3:32:34 PM
Last modification on : Wednesday, February 13, 2019 - 5:58:02 PM

File

giorgi-certification-midp.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

73

Files downloads

151