论文部分内容阅读
自从Goppa发现了有限域上代数曲线在编码上的应用,即代数几何码的构造后,很多编码、密码学者尝试从代数曲线的角度去研究编码和密码.近年来,密码中流密码体系中密钥流序列的构造及其线性复杂度的分析和编码中纠错码码字个数的渐近界这两个问题吸引了很多人的关注.本文主要利用有限域上平面代数曲线的算术理论(代数函数域理论)来研究这两个热点问题. 在流密码体系中,密钥流序列是元素取自有限域的伪随机序列.为了抵抗Berlekamp-Massey算法攻击,首先需要构造具有高线性复杂度的密钥流序列.同时基于对密码稳定性的考量,还需要构造具有高错误线性复杂度的密钥流序列. 对于非周期序列的情形,Xing-Lam利用函数在有理位的局部展开给出了单个非周期序列的构造,本文给出了Xing-Lam构造的单个非周期序列的错误线性复杂度的一个下界,并把Xing利用函数局部展开得到多重序列的构造推广到更一般的情形.对这样得到的多重序列,本文同样给出了其联合错误线性复杂度的一个下界. 对于周期序列的情形,将Xing-Ding-Kumar关于单个序列的构造推广到多重序列的情形,并证明这样得到的多重序列其联合线性复杂度及错误联合线性复杂度都可以很高.此外,基于函数域的自同构群的结构,利用函数域上函数在高次位的赋值及在有理位的赋值,给出多重周期序列的两种新的构造方法.分析并证明了当函数满足一定的条件时,这样得到的多重周期序列的联合线性复杂度和错误联合线性复杂度可以达到最大值,即等于周期.特别地,利用Hermitian函数域的相关性质,构造出三类多重周期序列.证明了当错误个数小于重数减2时,其错误联合线性复杂度可达到多重序列的周期. 在纠错码码字个数的渐近界方面.本文考虑两类特殊的码:常重复合码和二元自正交码.对于常重复合码,本文利用剩余多项式环给出常重复合码的一个构造.当固定最小距离d和码长n时,此构造给出了的常重复合码最大码字个数Aq(n,d,[ω0,…,ωq-1])的一个下界.当最小距离d=3时,这个下界改进了Luo等给出的一个下界.而当最小距离d≥4时,据我们所知,目前还没有其他关于Aq(n,d,[ω0,…,ωq-1])的下界.特别地,当最小距离d=5,我们构造的常重复合码的码字个数和最优的码字个数达到同一个数量级. 对于二元自正交码,本文证明了该码是渐近达到Gilbert-Varshamov界的.此外,我们给出了二元自正交码的两类构造:一类是利用达到Tsfasman-Vladut-Zink界的代数几何码和一些性质良好的二元正交码的链接码:另一类是借助达到Tsfasman-Vladut-Zink界的代数几何码在自对偶基给定的映射下的像.通过这两种构造给出了信息率R和相对最小距离δ之间的关系.当信息率R=1/2时,可以得到一簇相对最小距离δ≈0.0595的二元自正交码,此时构造得到的码很接近Gilbert-Varshamov界. 本文还研究了周期序列和循环码、多重周期序列和1-生成拟循环码之间的对应关系,利用这种对应关系给出周期序列和多重周期序列的复杂度分布,部分回答Niederreiter的一个公开问题.此外,利用代数函数域的自同构在有理位集合上的作用给出了拟循环码的构造.特别地,在Hermitian函数域上得到了三类拟循环码,并且这样得到的拟循环码具有良好的编码译码算法.