有限域上一元方程求解和相关问题的研究

发布时间：2017-04-06 12:07

  本文关键词：有限域上一元方程求解和相关问题的研究，，由笔耕文化传播整理发布。

【摘要】：本文中我们主要对数论和密码学中出现的有限域上的一元方程求解问题和相关问题进行了探讨,主要包括有限域上的平方根计算,三次根计算,高次根计算和素性判定等问题。首先,我们给出一个确定性算法来计算有限域Fq上的平方根。我们的算法通过构造一个和Fq×Fq同构的多项式环,然后在该环上完成计算。我们算法的运行时间为O(t log t log q+log2 q),其中q-1=2st。当t=poly(log q)时,我们的算法是确定的多项式时间算法。同时我们将该算法应用到Proth素数判定中,当t为O((log q)2)时,我们的算法是目前已知的最优Proth素性判定算法。其次,我们将Sze在有限域Fq上计算平方根的确定性算法扩展为随机算法,其中q-1=2st。我们算法的期望运行时间为O((log q)2)。和TonelliShanks算法相反,我们的随机算法在s越大时,其每次随机选择成功的概率越高,相比原始的Sze算法,我们的随机算法不需要计算ζ4。再次,我们使用Lucas序列给出了有限域Fp上计算平方根的三个算法,我们先使用Vn(P,Q)直接构造了一个随机算法来计算Fp上的平方根,其期望运行时间为4.5 log p次Fp上的乘法操作。然后我们使用Vn(P,1)构造了一个确定性算法来计算有限域上的平方根,该算法恰好能对(p-1)/4+1个二次剩余计算平方根。之后我们将该确定性算法扩展成一个随机算法,其期望运行时间为2 log p次Fp上的乘法操作。再次,我们将Berlamp算法计算有限域Fq上平方根的随机算法扩展到对x3=a的方程的求解,同时使用分圆理论给出其算法分析。与以往的算法不同的是,我们使用二次剩余理论对三次方程进行求解,计算的过程中并不需要寻找三次非剩余,同时我们也将这一方法扩展到对Fq上任意的三次方程x3+ax2+bx+c=0的求解。最后,我们将Cipolla-Lehmer算法计算有限域Fq上平方根的随机算法通过计算Fq扩域Fqr上元素范数的方法扩展到对方程xr=a的求解,其中r为素数幂。我们通过构造Fq[X]上的不可约多项式f(x)给出我们的算法,其中deg(f)=r且f(x)的常数项为(-1)ra。同时我们利用Davenport-Hasse关系和Double Counting技术,给出我们构造f(x)算法的分析。对满足r4≤q的r,我们的算法是非常有效的。
【关键词】：平方根 有限域 确定性算法 随机算法
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O153.4
【目录】：

• 摘要5-7
• ABSTRACT7-13
• 第一章 绪论13-21
• 1.1 问题概述13-14
• 1.1.1 平方根问题概述13-14
• 1.1.2 高次根问题概述14
• 1.2 研究背景及意义14-17
• 1.2.1 计算数论中的应用15
• 1.2.2 Rabin密码系统中的应用15-16
• 1.2.3 椭圆曲线上点压缩的应用16-17
• 1.3 相关工作17-20
• 1.4 内容组织20-21
• 第二章 预备知识21-27
• 2.1 基础数论21-22
• 2.2 抽象代数22-25
• 2.3 有限域25
• 2.4 算法和操作复杂性25-27
• 第三章 确定性算法计算有限域上的平方根27-35
• 3.1 同构环介绍27-28
• 3.2 确定性算法28-32
• 3.3 素性测试中的应用32-33
• 3.4 结论33-35
• 第四章 随机算法计算有限域上的平方根35-39
• 4.1 Sze群同构35-36
• 4.2 随机算法36-38
• 4.3 结论38-39
• 第五章 使用Lucas序列构造F_p上的平方根算法39-51
• 5.1 Lucas序列背景知识介绍39-41
• 5.2 几个重要引理41-42
• 5.3 随机算法142-44
• 5.4 确定性算法44-48
• 5.5 随机算法248-50
• 5.6 结论50-51
• 第六章 有限域上三次根的求解51-61
• 6.1 扩展Berlekamp算法求解三次根51-57
• 6.1.1 x~3=a全部根的求解57
• 6.2 对F_p~*上任意三次方程的求解57-59
• 6.3 结论59-61
• 第七章 有限域上高次根的求解61-67
• 7.1 Cipolla-Lehmer平方根算法61-62
• 7.2 Cipolla-Lehmer算法扩展到r次根62-63
• 7.3 构造常数项为(-1)~ra的不可约多项式63-66
• 7.4 结论66-67
• 全文总结67-69
• 参考文献69-77
• 致谢77-78
• 攻读学位期间发表的学术论文目录78-79
• 附件79

【相似文献】

中国期刊全文数据库 前10条

1 王泽涵;有限域上一类多项式的周期[J];电子学报;1984年05期

2 李复中;关于Golomb猜想[J];科学通报;1984年15期

3 周大术;有限域的一个特征性质[J];西南师范学院学报(自然科学版);1985年02期

4 郝长亮;有限域上一类n元二次方程解的个数[J];数学的实践与认识;1986年01期

5 刘光明;关于有限域G上的某些方程解组的计数问题[J];郑州轻工业学院学报;1995年01期

6 王文松,孙琦;有限域上一类方程解数的直接公式[J];数学年刊A辑(中文版);2005年03期

7 李志慧;;特征为2的有限域上一类正形置换多项式的非存在性[J];陕西师范大学学报(自然科学版);2008年02期

8 曹喜望;;有限域上几个置换多项式及一个密钥交换协议[J];数学学报;2009年05期

9 许广魁;;有限域上一类方程在(F~*)~n中的解数公式[J];绵阳师范学院学报;2010年02期

10 师连城;有限域上的方程[J];四平师院学报(自然科学版);1981年00期

中国重要会议论文全文数据库 前5条

1 丁金扣;黄铮;温巧燕;杨义先;;有限域上的多输出正交函数[A];2005通信理论与技术新进展——第十届全国青年通信学术会议论文集[C];2005年

2 周旋;王秋艳;端木庆峰;瞿成勤;;有限域上幂函数S盒构造及性质研究[A];2013年中国信息通信研究新进展论文集[C];2014年

3 张仲明;马立波;;基于有限域的结构化LDPC码构造[A];第七届卫星通信新技术、新业务学术年会论文集[C];2011年

4 金栋梁;赵亚群;;有限域上逻辑函数的Chrestenson谱的性质[A];2007通信理论与技术新发展——第十二届全国青年通信学术会议论文集（上册）[C];2007年

5 李小平;李宁;刘彦明;董庆宽;;一种基于ONB的ECC有限域算术的设计和FPGA优化实现[A];第八届全国信号与信息处理联合学术会议论文集[C];2009年

中国博士学位论文全文数据库 前5条

1 邓明立;有限域思想的历史演变[D];河北师范大学;2004年

2 曹炜;有限域上的一些算术问题[D];四川大学;2007年

3 李银;椭圆曲线密码中的有限域算术运算研究[D];上海交通大学;2011年

4 王健;椭圆曲线加密体制的双有限域算法及其硬件实现[D];北京大学;2008年

5 王冠军;基于PSA和有限域理论的高级综合研究[D];哈尔滨工程大学;2009年

中国硕士学位论文全文数据库 前10条

1 王忠有;RFID安全协议的研究与设计[D];电子科技大学;2014年

2 靳琴琴;有限域上的坐标环的性质及三角分解[D];电子科技大学;2014年

3 李哲;有限域上一元方程求解和相关问题的研究[D];上海交通大学;2015年

4 罗艳梅;有限域上一类特殊方程的解数公式[D];南京航空航天大学;2009年

5 韩芳;有限域快速多项式相乘运算核的研究[D];华东师范大学;2005年

6 沈晓强;有限域乘除法研究与实现[D];国防科学技术大学;2006年

7 贾美;有限域上置换多项式的构造[D];南京航空航天大学;2012年

8 董可静;有限域生成元的若干性质研究[D];南京航空航天大学;2010年

9 余杜鹃;有限域上一类方程的解数[D];宁波大学;2014年

10 吕芳妮;有限域上的置换多项式[D];南京师范大学;2014年

  本文关键词：有限域上一元方程求解和相关问题的研究，由笔耕文化传播整理发布。

本文编号：288832