ON MULTIPLICATION OF POLYNOMIALS MODULO A POLYNOMIAL

作     者：WINOGRAD, S 

出 版 物：《SIAM JOURNAL ON COMPUTING》 

年 卷 期：1980年第9卷第2期

页      面：225-229页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：complexity of computations multiplicative complexity product of polynomials 

摘      要：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}}$.