Design and implementation of polynomial matrix multiplication by using cyclic convolution technique

Abstract

This work presents a mathematical framework for the development of efficient algorithms for cyclic convolution computations. The framework is based on the Chinese Reminder Theorem (CRT) .In particularly, this work focuses on the arithmetic complexity of a matrix-vector product when this product represents a CC computational operation or it represents a polynomial multiplication modulo the polynomial z N-1, where N represents the maximum length of each polynomial factor and it is set to be a power of 2. The proposed algorithms are compared against existing algorithms developed making use of the CRT and it is shown that these proposed algorithms exhibit an advantage in computational efficiency. They are also compared against other algorithms that make use of the Fast Fourier Transform (FFT) to perform indirect CC operations, thus, demonstrating some of the advantages of the proposed development framework.