有限域Fp～2的原根求法及其应用研究

论文摘要

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

论文目录

• 摘要
• 第一章 引言
• p的原根出发求F_p²的原根的算法)'>1.1 霍-张算法(一个从F_p的原根出发求F_p²的原根的算法)
• 2序列方面的研究成果'>1.2 原根在B₂序列方面的研究成果
• 1.3 原根在剩余理论方面的研究成果
• 1.4 本文的主要工作
• 第二章 预备知识
• 2.1 有限域的基本性质
• 2.2 四次剩余特征的基本性质
• 2.3 时间复杂度的基本概念
• 2.4 一些基本算法的时间复杂度
• p²的原根求法'>第三章 有限域F_p²的原根求法
• 3.1 几个引理
• 3.2 算法的改进、分析和比较
• 3.3 具体算例
• 第四章 原根的应用研究
• 2序列方面的应用研究'>4.1 原根在B₂序列方面的应用研究
• 4.2 原根在剩余理论方面的应用研究
• 参考文献
• 附件：两篇已发表论文首页