New Efficient Algorithms for Multiplication Over Fields of Characteristic Three

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 (mathbb {F}_{3^{n}}) where n≥1. We then derive a 3-way polynomial multiplication algorithm with five 1/3 sized multiplications that use interpolation in (mathbb {F}_{9}). 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 (mathbb {F}_{3}) and (mathbb {F}_{9}). The final proposal is a new 3-way polynomial multiplication algorithm over (mathbb {F}_{3}) that uses three polynomial multiplications of 1/3 of the original size over (mathbb {F}_{3}) and one polynomial multiplication of 1/3 of the original size over (mathbb {F}_{9}). 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.