MINIMUM COMPLEXITY AND LOW-WEIGHT NORMAL POLYNOMIALS OVER FINITE FIELDS

Abstract

In this paper, by using some algorithms, the distribution of the complexity of normal polynomials over finite fields of characteristic three with degree extensions up to 16 is provided.  Also, the current results on the smallest known complexity for the remaining degree extensions up to 300 by using a combination of theorems and known exact values are given.  In what follows, by using some algorithms, a table of normal trinomials and pentanomials with minimum complexity among all normal trinomials and pentanomials, respectively over \(\mathbb{F}\)₃, with their complexities for each degree n with 3ⁿ ≤ 10⁵⁰ is presented.  Also, either normal trinomials or pentanomials with minimum weight over \(\mathbb{F}\)₃, for each n, 106 ≤ n ≤ 300 are listed.