有限域上(n,k)(k\geq 3)型高斯正规基的对偶基的复杂度

The complexity of the dual bases for Gauss normal bases of type (n,k)(k\geq 3) over finite fields

摘要:

熟知, 有限域上的正规基在计算机的软件和硬件实现中都有广泛的作用, 尤其令人感兴趣的是确定有限域上的正规基, 特别是高斯正规基的复杂度. 通过利用有限域的性质与初等的技巧, 给出了有限域上一类(n,k)(k\geq 3)型高斯正规基的对偶基的复杂度的上下界, 由此确定了有限域上(n,k)(k=1,2)高斯正规基的对偶基的准确复杂度, 从而简化了万哲先等人在2007年给出的证明.

Abstract:

It is well known that normal bases over finite fields have been implemented efficiently in software. The hardware and time complexity of multiplication using normal bases depends on the structure of the normal basis used, particularly on the complexity of the normal basis. Therefore to determine the complexity for normal bases, especially Gauss normal bases over finite fields, is interesting. By properties for finite fields and elementary techniques, we obtain the upper and lower bounds of the complexity for the dual basis of a class of the type (n,k)(k\geq 3) Gauss normal bases, and determine the explicit complexity of the dual basis for the type (n,k)(k=1,2) Gauss normal bases over finite fields, which is an elementary proof for the main results given by Wan and Zhou in 2007.