【作者】 孙翠芳；

【导师】 张振祥；

【作者基本信息】 安徽师范大学 ， 应用数学， 2005， 硕士

【摘要】 记F_q为含q=pⁿ个元素的有限域,这里p是素数,n是正整数。域F_q中的非零元F_q^*=F_q\{0}关于乘法构成一个循环群F_q^*=（θ）,其生成元θ称为域F_q的一个原根。密码界公认为椭圆曲线公钥密码体制是最有前途的公钥密码体制,在椭圆曲线公钥密码体制中,要计算有理点的数目,一个公认为有效的Schoof算法需要用到p是奇素数时有限域F_p²的原根。另外,B₂序列和剩余理论等方面也要用到有限域F_p²的原根。霍家佳和张起帆（四川大学学报（自然科学版）,40:3（2003）,447-452.MR 2004d:11122）给出了一个从有限域F_p的原根出发求F_p²的原根的算法（简称霍-张算法,共含三大步）,但对算法的时间复杂度没有给出定量分析。 本文的主要结果分为两部分。在第一部分（第三章）,我们在不改变霍-张算法整体框架（即三大步）的前提下,利用关于原根的基本性质来改进这个算法的三大步,特别利用一个已知的关于原根的充要条件来改进这个算法的第三步,改进后的算法三步运算量分别是原算法三步运算量的1/4或有数量级的减少不等,并且给出一个算例来具体体现改进后的算法的运算量的减少程度。在第二部分（第四章）,我们利用F_p²的原根的性质,给出了特殊B₂序列元素间的一些关系和几个特殊原根的极小多项式;再利用F_p的原根的性质,构造了具有相反Legendre符号的连续整数,推广了孙智宏关于集合Q_r（p）={k:（k+i/p）₄=i^r,k∈F_p}（r=0,1,2,3）与平方剩余之间的关系,并且给出了集合Q_r（p）所包含的元素的个数之间的关系,这里p是奇素数,（（?））是Legendre符号,（（?））₄是四次剩余符号,i=-1^1/2。更多还原

【Abstract】 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)更多还原