New Algorithms Over Integer Rings

The CRT has been widely employed in designing computationally efficient algorithms in digital signal processing. It has two versions. One is over a ring of integers and the second is over a ring of polynomials with coefficients defined over a field. In this chapter, we extend the CRT to the case of a ring of polynomials with coefficients defined over a finite ring of integers. The entire work is correlated to the already established results on finite fields. This extension serves as a keystone in the design of number theoretic algorithms for performing some of the most computationally intensive tasks. This approach is far superior to the NTTs in the sense that the limitations on both the word length and the sequence length are completely removed. In fact, the NTTs may be considered as a very special case of the general approach. Furthermore, all the computations required in this approach, which inherits the merits of the CRT, can be performed in parallel.