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.