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 (SCI-Expanded) identifier identifier

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.