Galois 环上序列的研究

姓    名：张晓磊    学科专业：信息安全

研究方向：密码学    指导教师：胡磊教授

摘      要

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

1.我们研究了 Galois 环上多项式的周期。Galois 环上线性递归序列的周期可以通过序列特征多项式的周期来刻画。R上的多项式 f(x) 总可以分解成 f₁(x)f₂(x)…f_k(x), 其中诸f_i 两两互素, 且f_i(x) 模p为域上某个既约多项式的方幂, 而f(x)的周期为这些f_i周期的最小公倍数。对于f(x)模p为R上某 n次既约多项式的m次方幂, 我们在R的n次Galois扩张S上将f(x) 分解为g₁(x)g₂(x)…g_l(x), f(x)的周期与这些g_j(x)的周期相同, 其中g_j(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的拟周期是θ的拟阶。将θ写成θ₀θ₁ 的形式, 其中θ₀在 Teichmüller 集中, 而 θ₁=1模p, 则θ的拟阶是θ₀,θ₁拟阶之积。我们证明了θ₀的拟阶由θ的阶完全显式地确定。Galois环上序列的拟周期通常不可避免, 为此我们给出了本质拟周期的概念, 给出了序列不存在本质拟周期的判定方法。

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

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