On the arithmetic operations over finite fields of characteristic three with low complexity (Q2349632)

Finite fields of sizes \(3^n\) have recently been used for cyptographic purposes, where the field operations need to be implemented efficiently. The most important such operation is multiplication, which can be split into polynomial multiplication and reduction modulo a generating polynomial. The number of nonzero coefficients of this generating polynomial should be as small as possible, since this determines the efficiency of reduction. This article begins with details of representing finite fields of characteristic 3 using Hermite polynomials. The explicit simple form of the Hermite polynomials in \({\mathbb F}_{3}\) is derived. A formula for the result of polynomial multiplication of two Hermite polynomials is given and calculations with polynomials of 2,3 and 4 terms are carried out explicitly. In theorem 2, the authors state the complexity of multiplication and addition when the Hermite polynomial representation and a divide-and-conquer idea are used. The authors derive the form of sums of two Hermite polynomials which can be irreducible for certain degrees and which have the smallest reduction complexity. Then a comparison of these sums as reduction polynomial with the irreducible polynomial \(f(x) = x^n + x^2 + 2\) is made. In theorem 3, the authors give the number of additions and scalar multiplications of reduction modulo such a sum of two Hermite polynomials. These numbers are compared to the numbers which arise when the standard polynomial is used. Finally, the authors discuss the product of two polynomials expressed as matrix vector product, again in the context of Hermite polynomial representation in \({\mathbb F}_{3}\).