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, vol.90, no.3, pp.285-294, 2018 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 90 Issue: 3
  • Publication Date: 2018
  • Doi Number: 10.1007/s11265-017-1234-x
  • Title of Journal : JOURNAL OF SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY
  • Page Numbers: pp.285-294

Abstract

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.