有限域上本原多项式的研究

论文摘要

本原多项式的分布问题是计算数论中的一个基本问题,在密码学,编码理论,数字水印等诸多领域都有重要应用。1992年,Tom Hansen与Gary L.Mullen[34]提出了关于Fq上指定任意单系数的本原多项式存在性的猜想,即著名的Hansen-Mullen猜想。由于直接计算多项式系数十分困难,可以通过p-adic分析,指数和,筛不等式等工具,将其分解为一系列简单的充分条件。本文根据S.D.Cohen的工作,对指定单系数的次数高于9次本原多项式的存在性进行了研究。本文另外对有限域上的多项式算法进行了研究,包括基本算法,不可约多项式搜索算法,多项式分解以及本原多项式搜索算法。了解本原多项式的分布情况,可以对搜索特殊性质的本原多项式起到指导作用。根据本原多项式的定义搜索本原多项式,涉及有限域上的本原根以及极小多项式的计算,时间空间复杂度很大,并且不能先验指定特定项的系数,不能作为有效的搜索算法。本文利用本原多项式的性质设计筛式算法,对候选多项式进行判定,极大减小了运算规模。这是本论文的创新点。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 研究背景
• 1.2 相关领域的研究进展
• 1.3 研究目的和方法
• 1.4 文章结构
• 第二章 基础数学知识
• 2.1 p-adic数及Galois环
• 2.2 Galois环上的特征和
• 2.2.1 Galois环上的特征和
• 2.2.2 Galois环上的特征和估计
• 2.3 Galois环上的正规元
• 2.4 Galois环上的提升本原多项式
• 第三章 指定单系数的本原多项式
• 3.1 问题重述
• 3.2 问题分析
• 3.2.1 情况分类
• 3.2.2 本原元与κ-自由元
• 3.2.3 p-adic表示
• 3.2.4 充分性判定准则
• 3.2.5 筛方法
• 3.2.6 特征函数
• 3.3 标准问题
• 3.3.1 标准问题:一般情况
• 3.3.2 标准问题:低次情况
• 3.3.3 标准问题:偶系数项情况
• 3.4 零问题
• 3.5 规范问题
• 3.6 本章小结
• 第四章 多项式算法分析
• 4.1 基本算法
• 4.1.1 加法与减法
• 4.1.2 乘法
• 4.1.3 除法
• 4.1.4 模运算
• 4.1.5 重复平方法
• 4.1.6 Hornor算法
• 4.1.7 欧几里得算法
• 4.1.8 逆运算
• 4.1.9 中国剩余定理
• 4.2 不可约多项式搜索算法
• 4.2.1 多项式可约性检验
• 4.2.2 Berlekamp可约性检验算法
• 4.2.3 不可约多项式构造算法
• 4.3 多项式分解算法
• 4.3.1 算法框架
• 4.3.2 无平方因子分解
• 4.3.3 异次因子分解
• 4.3.4 同次因子分解
• 4.4 本原多项式搜索算法
• 4.4.1 本原多项式基本性质
• 4.4.2 指定系数本原多项式搜索算法
• 4.5 本章小结
• 第五章 总结
• 参考文献
• 致谢
• 答辩决议书