\input zb-basic
\input zb-ioport
\iteman{io-port 05920424}
\itemau{Cenk, Murat; \"Ozbudak, Ferruh}
\itemti{Multiplication of polynomials modulo $x^{n}$.}
\itemso{Theor. Comput. Sci. 412, No. 29, 3451-3462 (2011).}
\itemab
Summary: Let $n,\ell $ be positive integers with $\ell \leq 2n - 1$. Let $\cal R$ be an arbitrary nontrivial ring, not necessarily commutative and not necessarily having a multiplicative identity, and let $\cal R[x]$ be the polynomial ring over $\cal R$. In this paper, we give improved upper bounds on the minimum number of multiplications needed to multiply two arbitrary polynomials of degree at most $(n - 1)$ modulo $x^{n}$ over $\cal R$. Moreover, we introduce a new complexity notion, the minimum number of multiplications needed to multiply two arbitrary polynomials of degree at most $(n - 1)$ modulo $x^{\ell }$ over $\cal R$. This new complexity notion provides improved bounds on the minimum number of multiplications needed to multiply two arbitrary polynomials of degree at most $(n - 1)$ modulo $x^{n}$ over $\cal R$.
\itemrv{~}
\itemcc{}
\itemut{multiplication of polynomials; multiplicative complexity; multiplication algorithms; multiplication of power series}
\itemli{doi:10.1016/j.tcs.2011.02.031}
\end