关于有限域F_p^2上的原根求法的注记

Notes on an Algorithm for Finding Primitive Roots of Finite Field F_p^2

在四川大学学报(自然科学版)2003年第3期"关于有限域Fp2上的原根"一文中,霍家佳等给出了一个从有限域Fp的原根出发求Fp2的原根的算法,这个算法共含三大步.在本文中,在不改变霍文算法整体框架(即三大步)的前提下,作者利用关于原根的基本性质改进了这个算法的三大步,特别利用一个已知的关于原根的充要条件改进了这算法的第三步.改进后的算法三大步运算量分别是原算法三大步运算量的1/4或有数量级的减少不等.最后给出一个算例来具体体现改进后的算法的运算量的减少程度.

Huo and Zhang presented in a recent paper ('About the Primitive Root of Finite Field F_(p^2)', Journal of Sichuan University (Natural Science Edition), Vo1.40, No.3, (2003), pp.447-452) an algorithm for finding primitive roots of a finite field F_(p^2). The algorithm contains three main steps. In this paper, the author uses some basic properties of primitive roots to improve the three main steps, especially uses a well-known sufficient and necessary condition on primitive roots to improve the third main step. The arithmetic labor of the improved three main steps is a quarter of or magnitude-order less than that of the original three main steps. Then the author gives an example to show the difference between the arithmetic labor of both algorithms.