第3期 孙霓刚等：Galois环上的一类GMW序列及其线性复杂度 ·25·Galois环上的一类GMW序列及其线性复杂度孙霓刚1,2，胡磊2(1. 华东理工大学 计算机科学与工程系，上海 200237；2. 中国科学院研究生院 信息安全国家重点实验室，北京 100049)摘 要：将有限域上GMW序列的概念推广到了一般的Galois环上利用环上的置换，定义了一类新的一般Galois环上的GMW序列，并对其线性复杂度进行了估计结果表明，这类GMW序列具有非常大的线性复杂度关键词：密码学；GMW序列；线性复杂度；Galois环中图分类号：TN918.1 文献标识码：A 文章编号：1000-436X(2008)03-0023-04GMW sequences over Galois rings and their linear complexitiesSUN Ni-gang 1,2, HU Lei 2(1. Department of Computer Science and Engineering, East China University of Science and Technology, Shanghai 200237, China;2. State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences,Beijing 100049, China)Abstract: A new family of GMW sequences over an arbitrary Galois ring was defined. This generalizes the concept of GMW sequences over finite fields. Upper and lower bounds on the linear complexities of this family of GMW sequences were investigated and the result shows that such sequences have large linear complexities.Key words: cryptography; GMW sequence; linear complexity; Galois ring1 引言扩频通信因其良好的抗干扰能力，不仅在军事通信中获得了成功应用，而且也越来越广泛地应用到了民用通信中。
在扩频多址通信中，扩频码的性能有着举足轻重的作用，它的好坏将直接影响到整个系统性能的优劣而在扩频码的所有特性中，一个很重要的指标就是线性复杂度，只有具有大线性复杂度的序列才能够不被别人轻易地破译因此如何构造出具有大线性复杂度的扩频序列成了人们研究的一个热点[1]1984年，Scholtz和Welch利用迹函数构造出了有限域上的GMW序列[2]人们发现此序列不仅和m序列一样具有理想的自相关性，而且对于相同周期的两种序列，GMW序列的线性复杂度和平移不等价序列个数要比m序列大得多从此，人们开始了对GMW序列及其线性复杂度的研究[3~8]2000年，Udaya和Siddiqi将有限域上GMW序列的概念进行了推广，构造出了四元Galois环Z4上的GMW序列[9]研究发现，在周期相同的情况下，这种Galois环上的GMW序列要比有限域上的GMW序列具有更大的线性复杂度以及更多的序列个数在本文中，将进一步推广Udaya和Siddiqi的工作，构造出一类新的一般Galois环上的GMW序列，并对其线性复杂度进行研究结果表明，构造得到的这类GMW序列仍然具有非常大的线性复杂度收稿日期：2007-01-05；修回日期：2008-01-05基金项目：国家自然科学基金资助项目（60373041, 90104034）Foundation Item: The National Natural Science Foundation of China (60373041, 90104034)本文中假设p为任意素数，e, r, u为任意正整数。
用表示具有特征pe及阶per的Galois环，用R’表示具有特征pe及阶peru的Galois环R中所有的可逆元组成了一个乘法群，记为同样地，把中所有的可逆元所组成的群记为可以表示成它的2个乘法子群的直积，即，其中是阶为的循环群，是阶为的子群并且其每个元素的阶均整除中任意元素均可以表示成=，其中，用表示从到的迹函数，表示从到整数剩余类环的迹函数有关Galois环的内容请参见文献[10,11]2 环上GMW序列本节中将构造一类Galois环上的GMW序列2.1 R上的置换假设b为任意正整数且满足，对于中任意元素＝，其中，定义映射：满足 引理1 是上的置换证明 任取整数满足，只需证明在上是单射即可设，是中任意2个元素，其中若 ，则有， (1)其中，，式(1)两边同进行次方，得到设，，其中，代入式(1)可得考虑到的阶整除且，从而进而有，其中由于与互素，故存在整数满足，从而 (2)其中，，式(2)两边同乘以，得到，进而因此是上的单射2.2 构造GMW序列设是中阶为的本原元以及利用上面定义的置换，构造Galois环上的GMW序列 并且定义Galois环上的GMW序列族GGMW GGMW由于是上的置换，故具有周期。
3 线性复杂度本节我们将讨论GGMW中序列的线性复杂度定义1 我们称多项式 是上周期序列的联接多项式，如果其系数满足如下关系 定义2 上周期序列的线性复杂度（LC）定义为 是的联接多项式引理2[12] 设是周期为的序列则多项式是的联接多项式定义3[13] 设是上周期为的序列任取Galois环中的本原元，则的离散傅立叶表示为 其中 定理1 设是上周期为的序列的线性复杂度等于的离散傅立叶表示中非零系数的个数，即 证明 假设在中共有个，记为，使得考虑到，则有如下关系令，则的所有根均为的根由引理2可知，是的一个联接多项式，从而若，则存在的联接多项式满足再次利用引理2，可得中满足的的个数<，与假设矛盾以下假设对中的任意元素，定义上的变换 任取GGMW中序列，其中利用可得到如下分解 定义序列 从而有 (3)将b按p展开，可写成如下形式 其中1，0，H是b的按p展开式中非零系数的个数引理3 序列的线性复杂度 证明 易见同构于一条元GMW序列，因此利用文献[6]中定理2，我们有再利用的离散傅立叶表示以及定理1，可得引理4 序列的线性复杂度 证明 令，则可以表示为，其中 ，即可以表示为至多个的不同幂次的线性和。
如果我们将的通项展开，则可以得到一个的不同幂次的线性和，并且其中所含的的幂次最多是个根据定理1，我们有有以下引理引理5[6] 假设是有限域中的本原元定义上的序列，则在的每一个长的连续片断中，恰好含有个零引理6 假设是Galois环中的本原元对任意，定义上的序列，其中，则在的每一个长的连续片断中，恰好含有个的理想中的元素证明 易见同构于引理5中定义的某条序列因此由引理5可知，在的每一个长的连续片断中恰好含有个零考虑到，引理得证引理7 序列的线性复杂度 证明 不妨假设序列且非零令 其中由的定义以及引理6可知，不全为零假设是中全部的非零项易见是中的零因子，由 可知，中的非零项是以为周期重复的令, 我们有 任取，，其中当时，其中，有；当时，其中，有此时不为零因此在中使得的的个数至多为下面证明中使得的的个数至多为否则，假设中使得的的个数>任取使得由的定义知道，从而其中是相对于的广义Frobenius自同构[11]由,从而存在使得 ，进而这就说明了每一个使得的，都对应于一个使得并且易见在这种对应方式下，如果对于且,存在对应的使得，则必有。
从而中使得的的个数>，矛盾因此我们证明了中使得的的个数至多为最后根据定理1，我们有序列的线性复杂度 最后利用式（3）、引理3、引理4以及引理7，就可以得到如下定理定理2 序列族GGMW中序列的线性复杂度满足 参考文献：[1] KUMAR P V. Frequency hopping code sequences designs having large linear span[J]. IEEE Trans Inf Theory, 1988, 34(1): 146-151.[2] SCHOLTZ R A, WELCH L R. GMW sequences[J]. IEEE Trans Inf Theory, 1984, 30(3): 548-553.[3] ANTWEILER M, BÖMER L. Complex sequences over GF(pm) with a two-level autocorrelation function and a large linear span[J]. IEEE Trans Inf Theory, 1992, 38(1): 120-130.[4] KLAPPER A, CHAN A H, GORESKY M. Cascaded GMW sequences[J]. IEEE Trans Inf Theory, 1993, 39(1): 177-183.[5] CHUNG H, NO J S. Linear span of extended sequences and cascaded GMW sequences[J]. IEEE Trans Inf Theory, 1999, 45(6): 2060-2065.[6] 朱近康, 李世鹏. P元GMW序列[J]. 中国科学技术大学学报, 1991, 21(4): 433-446.ZHU J K, LI S P. P-ary GMW sequences[J]. Journal of China University of Science and Technology, 1991, 21(4): 433-446.（下转第33页）。