On the reduction in multiplicative complexity achieved by the polynomial residue number system
G.S. Zelniker, Fred J. Taylor · IEEE Transactions on Signal Processing · 1992
The polynomial residue number system is known to reduce the complexity of polynomial multiplication from O(N/sup 2/) to O(N). A new interpretation of this complexity reduction is given in the context of associative algebras over a finite field. The new point of view provides a clearer understanding of the Chinese remainder theorem.>