Multiplication of polynomials modulo x(n)

CENK M., ÖZBUDAK F.

THEORETICAL COMPUTER SCIENCE, vol.412, no.29, pp.3451-3462, 2011 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 412 Issue: 29
  • Publication Date: 2011
  • Doi Number: 10.1016/j.tcs.2011.02.031
  • Journal Name: THEORETICAL COMPUTER SCIENCE
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.3451-3462
  • Keywords: Multiplication of polynomials, Multiplicative complexity, Multiplication algorithms, Multiplication of power series, 6-TERM, 5-TERM
  • Middle East Technical University Affiliated: Yes

Abstract

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.