Multiplication of polynomials modulo x(n)

CENK M., ÖZBUDAK F.

THEORETICAL COMPUTER SCIENCE, cilt.412, sa.29, ss.3451-3462, 2011 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 412 Sayı: 29
  • Basım Tarihi: 2011
  • Doi Numarası: 10.1016/j.tcs.2011.02.031
  • Dergi Adı: THEORETICAL COMPUTER SCIENCE
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.3451-3462
  • Anahtar Kelimeler: Multiplication of polynomials, Multiplicative complexity, Multiplication algorithms, Multiplication of power series, 6-TERM, 5-TERM
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.