Improved Polynomial Multiplication Formulas over F-2 Using Chinese Remainder Theorem

Cenk M., Oezbudak F.

IEEE TRANSACTIONS ON COMPUTERS, cilt.58, sa.4, ss.572-576, 2009 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 58 Sayı: 4
  • Basım Tarihi: 2009
  • Doi Numarası: 10.1109/tc.2008.207
  • Dergi Adı: IEEE TRANSACTIONS ON COMPUTERS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.572-576
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

Let n and l be positive integers and f(x) be an irreducible polynomial over F-2 such that ldeg(f(x)) < 2n - 1. We obtain an effective upper bound for the multiplication complexity of n-term polynomials modulo f(x)(l). This upper bound allows a better selection of the moduli when the Chinese Remainder Theorem is used for polynomial multiplication over F-2. We give improved formulas to multiply polynomials of small degree over F-2. In particular, we improve the best known multiplication complexities over F-2 in the literature in some cases.