有限维多项式代数的结构、算法及在编码密码学中的应用

论文摘要

本文的思想来源于密码学中的代数方程求解和代数免疫性研究.代数方程求解与多元多项式函数的性质有关,在布尔环中体现为真值表;代数免疫性与理想的性质有关,同时与乘法运算有着密切的联系.编码和密码学中的问题几乎都与高阶布尔环相关,元素和理想的性质就是刻画高阶布尔环代数结构以及相关算法.对于高阶布尔环的研究可以从三个不同的途径入手.其一是高阶布尔环是一个有限维的Artinian代数,从而可以从向量空间的角度描述其结构常数,从理想和子代数角度对其进行直和分解以及研究理想的结构和记数等,这种方法能很好地从理论上把握一个代数,但是不能从计算和表达上得到更好的结果;其二是从符号计算的角度出发,研究理想的生成元和求出向量空间的幂积基,这种研究的主要工具是Grobner基、吴方法和结式,这种研究方法的目的就是要进行精确计算从而给出计算和表达上的简单表示,但是计算的复杂度是双指数的;其三是多元插值,插值基是一组幂等乘积正交基,它能很好地对元素进行表示和进行乘法运算,但是多元插值的稳定性不是很好,插值基的计算也比较困难.本文综合利用了三种方法对高阶布尔环进行研究,同时给出了相关的一些应用.本文主要研究内容和结论包括:1、给出了单项式理想的生成元是正则列的充分必要条件,从而得到了从零维理想的Grobner基中选择极大正则列的方法.利用这些结果对一种基于计算机代数设计的门限方案的安全性进行了分析,指出了这种方案安全性是不完备的.2、提出了高阶布尔环的概念,并对其幂积基、乘积分解基和插值基的关系进行了刻画,进而得出了高阶布尔环是主理想环的结论.3、给出了高阶布尔环上元素的线性化表示方法,得到了多项式函数方程组的线性化求解算法,并且给出了布尔函数方程组线性化求解算法的复杂度估计.4、给出了高阶布尔环上函数的权和次数的一个关系.5、通过对一般高阶布尔环的研究,得到了相关的平行结论,提出了一种构造新型布尔环的方法.6、解决了两类基于完全非线性函数的线性码的权分布问题.

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 选题背景和意义
• 1.2 国内外相关研究和现状
• 1.3 本文的主要工作
• 1.3.1 研究思路
• 1.3.2 研究内容
• 第二章 预备知识
• 2.1 域上有限维代数的分解
• 2.2 有限维多项式代数的分解
• 2.3 代数攻击与有限域上的多变元方程组求解
• 2.4 编码的基本概念
• 2.5 多元多项式插值
• 2.6 矩阵的张量积与拉直变换
• 2.7 矩阵的Doolittle 分解
• 第三章 零维理想的正则列及其在门限方案中的应用
• 3.1 单项式理想
• 3.2 零维理想的Gr?bner 基与正则列
• 3.3 一种基于计算机代数的门限方案
• 3.4 基于计算机代数的门限方案的安全性分析
• 第四章 高阶布尔环的结构和应用
• 4.1 有限域上一元插值算法及其应用
• 4.2 高阶布尔环
• 4.2.1 高阶布尔环的向量空间基
• 4.2.2 多元Lagrange 插值基函数
• 4.2.3 多元Lagrange 插值基函数的正交幂等性
• qⁿ 中元素的顺序'>4.2.4 （?）_qⁿ中元素的顺序
• 4.3 高阶布尔环的结构和计算
• 4.3.1 高阶布尔环基的结构常数以及三组基之间的关系
• 4.3.2 高阶布尔环理想的结构和元素的乘积分解
• 4.4 高阶布尔环理论的应用
• 4.4.1 高阶布尔环上多项式函数方程组的线性化求解算法
• 4.4.2 布尔环上多项式函数方程组的线性化求解算法
• 4.4.3 高阶布尔环上平衡函数的次数及其相关问题
• 第五章 一般有限维多项式代数的结构和应用
• 5.1 一般高阶布尔环的结构
• 5.2 多元多项式插值
• 5.2.1 多元多项式的Lagrange 插值的幂积基
• 5.2.2 插值基和乘积分解基及其新算法
• 5.2.3 插值环的代数结构
• 5.3 有限维多项式代数的结构
• 5.4 新型布尔环的构造
• 第六章 两类基于完全非线性函数的线性码的权分布
• 6.1 完全非线性函数的原像分布
• 6.2 两类基于完全非线性函数的线性码的权分布
• 第七章 结束语
• 7.1 论文总结
• 7.2 进一步的研究工作
• 致谢
• 参考文献
• 作者在学习期间取得的学术成果