Article ID Journal Published Year Pages File Type
6874112 Information Processing Letters 2018 5 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,