On the reduction in multiplicative complexity achieved by the polynomial residue number system (Q4031499)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 149188
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the reduction in multiplicative complexity achieved by the polynomial residue number system |
scientific article; zbMATH DE number 149188 |
Statements
On the reduction in multiplicative complexity achieved by the polynomial residue number system (English)
0 references
1 April 1993
0 references
polynomial residue number system
0 references
polynomial multiplication
0 references
complexity reduction
0 references
associative algebras
0 references
finite field
0 references
0.8034794926643372
0 references
0.7907723188400269
0 references
0.7801998257637024
0 references
0.7797038555145264
0 references
\textit{A. Skavantzos} and \textit{F. J. Taylor} [IEEE Trans. Signal Process. 39, No. 2, 367-382 (1991; Zbl 0719.65012)] showed how to perform polynomial-type operations with reduced complexity. In particular the polynomial residue number system (PRNS) reduces the complexity of polynomial multiplication from \(O(N^ 2)\) to \(O(N)\). In this paper a new interpretation of this complexity reduction is given in the context of associative algebras over a finite field.
0 references
