New Efficient Algorithms for Multiplication Over Fields of Characteristic Three

CENK M., Zadeh F. H., Hasan M. A.

JOURNAL OF SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY, cilt.90, sa.3, ss.285-294, 2018 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 90 Sayı: 3
  • Basım Tarihi: 2018
  • Doi Numarası: 10.1007/s11265-017-1234-x
  • Dergi Adı: JOURNAL OF SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.285-294
  • Anahtar Kelimeler: Polynomial multiplication, Elliptic curves, Characteristic three fields, ELLIPTIC-CURVES, FORMULAS, MULTIPLIERS
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In this paper, we first present an enhancement of the well-known Karatsuba 2-way and 3-way algorithms for characteristic three fields, denoted by where nae1. We then derive a 3-way polynomial multiplication algorithm with five 1/3 sized multiplications that use interpolation in . Following the computation of the arithmetic and delay complexity of the proposed algorithm, we provide the results of our hardware implementation of polynomial multiplications over and . The final proposal is a new 3-way polynomial multiplication algorithm over that uses three polynomial multiplications of 1/3 of the original size over and one polynomial multiplication of 1/3 of the original size over . We show that this algorithm represents about 15% reduction of the complexity over previous algorithms for the polynomial multiplications whose sizes are of practical interest.