On An Algorithm For Finding Primitive Roots Of Finite Fields F_p～2 With Applications

Let F_q be a finite field with q = pⁿ elements where p is a prime and n a positive integer. The set F_q^* = F_q\{0} is a cyclic group F_q^* = (θ) under multiplication, its generator 0 is called a primitive root of F_q. In the elliptic curve public key crytosystems, for computing the number of rational points, the well-known Schoof algorithm needs the help of primitive roots of finite fields F_q² with p an odd prime. Primitive roots of finite fields F_p² also have applications in the study of B₂-sequences and the theory of residues. Huo and Zhang (Journal of Sichuan University, Natural Science Edition, Vol. 40, No. 3(2003), 447-452. MR 2004d:11122) presented an algorithm (called Huo-Zhang Algorithm for short) for finding primitive roots of finite field F_P². The algorithm contains three main steps without time complexity analysis.The main results of this paper devides into two parts. In the first part (Chapter 3), we use basic properties of primitive roots to improve the three main steps of the Huo-Zhang Algorithm, especially we use a well-known sufficient and necessary condition for 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. We also give an example to show the difference between the arithmetic labor of both algorithms. In the second part (Chapter 4), using the properties of primitive roots of F_p² and F_p, we first give some relations of elements in special B₂ sequences and the minimal polynomials of several special primitive roots; we then construct consecutive numbers with opposite Legendre symbols, generalize the relations between (r = 0,1,2,3) and quadratic residues given by Sun Zhihong, and give a relation of the number of elements of Q_r{p)...