有限域上高斯正规基及其对偶基的复杂度的准确计算关系（英文）

The Explicit Relationship of the Complexities Between Gauss Normal Bases and Their Dual Bases Over Finite Fields

熟知,作为一类低复杂度的正规基,有限域上的高斯正规基及其对偶基被广泛应用于编码、密码学、符号处理等领域.尤其确定高斯正规基及其对偶基的乘法表和复杂度问题,成为近年来的研究热点之一.本文完全确定了有限域上高斯正规基及其对偶基的乘法表和复杂度的对应关系,由此给出了文献[Acta Math.Sin.,Engl.Ser.,2006,22(3):845-848;Finite Fields Appl.,2007,13(4):411-417]中定理2的一个更为简单的证明.

It is well known that as a class of lower complexity normal bases over finite fields, Gauss normal bases and their dual bases are widely used in applications of finite fields in areas such as coding theory, cryptography and signal processing. Especially, to determine the multiplication table and complexity for Gauss normal bases and their dual bases is very interesting in recent years. In the present paper, the explicit relationship of the complexity between Gauss normal bases and their dual bases over finite fields is obtained. As corollaries, the explicit complexity for the dual basis of Type （n, k） （= 1, 2） Gauss normal basis over finite fields is obtained, which also gives a simpler proof for Theorems 2 in [Acta Math. Sin., Engl. Ser., 2006, 22（3）： 845-848; Finite Fields Appl., 2007, 13（4）： 411-417].