English  简体中文
搜索   
首页 中心概况 新闻动态 科研成果 研究队伍 技术园地 公共信息 联系我们

Galois 环上序列的研究


2011-05-18       


姓名:张晓磊

学科专业:信息安全

研究方向:密 码 学

指导教师:胡磊教授

摘      要

       周期序列在密码、编码、通信等领域有着广泛的应用。上世纪四五十年代以来,人们对有限域上的周期序列进行了广泛的研究,取得了丰硕的成果。上世纪 80 年代末, Galois 环上的序列开始成为大家关注的热点。与有限域相比, Galois 环上能提供更多性质良好的序列。但另一方面,Galois 环的结构比有限域复杂,因而研究起来也更困难。在本文中,我们对 Galois 环上序列的几个问题进行了研究,包括 Galois 环上序列的周期、拟周期、极大周期序列平移等价问题以及 Galois 环扩张的构造方法。具体地说, 主要贡献如下:

       1. 我们研究了 Galois 环上多项式的周期。Galois 环上线性递归序列的周期可以通过序列特征多项式的周期来刻画。R上的多项式 f(x) 总可以分解成 f1(x)f2(x)…fk(x), 其中诸fi 两两互素, fi(x) p为域上某个既约多项式的方幂, f(x)的周期为这些fi周期的最小公倍数。对于f(x)pR上某 n次既约多项式的m次方幂, 我们在RnGalois扩张S上将f(x) 分解为g1(x)g2(x)…gl(x), f(x)的周期与这些gj(x)的周期相同, 其中gj(x)p为某线性因式的m 次方幂。对于g(x)p (x-α)m, α∈S的情形, 我们引入一个与之相伴的多项h(x), h(x) p (x-1)m, 证明g(x)的周期可由h(x)的周期刻画, 并且h(x)的周期在绝大多数情形下达到一个由p, e, m参数决定的上界。

       2. 我们讨论了Galois环上不可约序列的拟周期问题。设θ为不可约序列s极小多项式的根, 我们证明了s的拟周期是θ的拟阶。将θ写成θ0θ1 的形式, 其中θ0 Teichmüller 集中, θ1=1p, θ的拟阶是θ0,θ1拟阶之积。我们证明了θ0的拟阶由θ的阶完全显式地确定。Galois环上序列的拟周期通常不可避免, 为此我们给出了本质拟周期的概念, 给出了序列不存在本质拟周期的判定方法。

       3. 我们研究了判定Galois环上两个极大周期序列平移是否等价的问题, 给出了求平移距离的一个算法。这两个问题是在Galois环上求解离散对数的问题。我们给出的算法先在有限域上计算离散对数, 然后通过迭代提升得到一系列模p的一次方程。如果这些方程都可解, 则序列是平移等价的, 通过求解这些方程, 可以求出平移距离。其计算复杂度主要集中在有限域离散对数的求解上。

       4. 我们研究了Galois环上相继的两个单扩张如何转化成一个单扩张的问题, 给出了一个求解最终扩张在基环上定义多项式的算法。
 
 
 

评论人:          
lois.local\

DCS 中心 版权所有
地址:北京市海淀区闵庄路甲89号 4号楼
联系电话:010-82546536 010-82546537
京ICP备05046059号