Title :
On the reduction in multiplicative complexity achieved by the polynomial residue number system
Author :
Zelniker, Glenn S. ; Taylor, Fred J.
Author_Institution :
Dept. of Electr. Eng., Florida Univ., Gainesville, FL, USA
fDate :
9/1/1992 12:00:00 AM
Abstract :
The polynomial residue number system is known to reduce the complexity of polynomial multiplication from O(N2 ) 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
Keywords :
algebra; computational complexity; digital arithmetic; number theory; polynomials; Chinese remainder theorem; associative algebras; complexity reduction; finite field; polynomial multiplication; polynomial residue number; Cathode ray tubes; Convergence; Convolution; Councils; Embedded computing; Equations; Galois fields; Helium; Polynomials;
Journal_Title :
Signal Processing, IEEE Transactions on
