Fast algorithms for computing one and two dimensional convolution in integer polynomial rings

Abstract

In this work, the factorization properties of polynomials defined over finite integer rings and the associated direct sums are analyzed. The objective is to describe new computationally efficient algorithms for computing one and two dimensional convolution of data sequences defined over finite integer rings. The number theoretical transforms (NTTs) are a special case of the general theory presented here.