Multiplication of polynomials modulo x(n)

Let n, l be positive integers with l <= 2n - 1. Let R be an arbitrary nontrivial ring, not necessarily commutative and not necessarily having a multiplicative identity and R[x] be the polynomial ring over 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 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(l) over 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 R. (C) 2011 Elsevier B.V. All rights reserved.