Multiplication of polynomials modulo x(n)


CENK M. , ÖZBUDAK F.

THEORETICAL COMPUTER SCIENCE, cilt.412, ss.3451-3462, 2011 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 412 Konu: 29
  • Basım Tarihi: 2011
  • Doi Numarası: 10.1016/j.tcs.2011.02.031
  • Dergi Adı: THEORETICAL COMPUTER SCIENCE
  • Sayfa Sayıları: ss.3451-3462

Ö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.