Multiplication of polynomials modulo xn

AbstractLet n,ℓ be positive integers with ℓ≤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 xn 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ℓ 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 xn over R