On Multiplication of Polynomials Modulo a Polynomial
Shmuel Winograd · SIAM Journal on Computing · 1980
The multiplicative complexity of the direct product of algebras $A_p $ of polynomials modulo a polynomial P is studied. In particular, we show that if P and Q are irreducible polynomials then the multiplicative complexity of $A_{\text{P}} \times A_{\text{Q}} $ is $2\deg ({\text{P}})\deg ({\text{Q}}) - {\text{k}}$, where k is the number of factors of P in the field extended by a root of ${\text{Q}}$.