galois环上的一类gmw序列及其线性复杂度

《galois环上的一类gmw序列及其线性复杂度》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3期孙霓刚等：Galois环上的一类GMW序列及其线性复杂度·25·Galois环上的一类GMW序列及其线性复杂度孙霓刚1,2，胡磊2(1.华东理工大学计算机科学与工程系，上海200237；2.中国科学院研究生院信息安全国家重点实验室，北京100049)摘要：将有限域上GMW序列的概念推广到了一般的Galois环上。利用环上的置换，定义了一类新的一般Galois环上的GMW序列，并对其线性复杂度进行了估计。结果表明，这类GMW序列具有非常大的线性复杂度。关键词：密码学；GMW序列；线性复杂度；Galois环中图分类号：TN918.1文献标识码：A文

2、章编号：1000-436X(2008)03-0023-04GMWsequencesoverGaloisringsandtheirlinearcomplexitiesSUNNi-gang1,2,HULei2(1.DepartmentofComputerScienceandEngineering,EastChinaUniversityofScienceandTechnology,Shanghai200237,China;2.StateKeyLaboratoryofInformationSecurity,GraduateUniversityofChines

3、eAcademyofSciences,Beijing100049,China)Abstract:AnewfamilyofGMWsequencesoveranarbitraryGaloisringwasdefined.ThisgeneralizestheconceptofGMWsequencesoverfinitefields.UpperandlowerboundsonthelinearcomplexitiesofthisfamilyofGMWsequenceswereinvestigatedandtheresultshowsthatsuchseque

4、nceshavelargelinearcomplexities.Keywords:cryptography;GMWsequence;linearcomplexity;Galoisring第3期孙霓刚等：Galois环上的一类GMW序列及其线性复杂度·25·1引言扩频通信因其良好的抗干扰能力，不仅在军事通信中获得了成功应用，而且也越来越广泛地应用到了民用通信中。在扩频多址通信中，扩频码的性能有着举足轻重的作用，它的好坏将直接影响到整个系统性能的优劣。而在扩频码的所有特性中，一个很重要的指标就是线性复杂度，只有具有大线性复杂度的序列才能够不被别人轻易地破

5、译。因此如何构造出具有大线性复杂度的扩频序列成了人们研究的一个热点[1]。1984年，Scholtz和Welch利用迹函数构造出了有限域上的GMW序列[2]。人们发现此序列不仅和m序列一样具有理想的自相关性，而且对于相同周期的两种序列，GMW序列的线性复杂度和平移不等价序列个数要比m序列大得多。从此，人们开始了对GMW序列及其线性复杂度的研究[3~8]。2000年，Udaya和Siddiqi将有限域上GMW序列的概念进行了推广，构造出了四元Galois环Z4上的GMW序列[9]。研究发现，在周期相同的情况下，这种Galois环上的GMW序列要比有限域

6、上的GMW序列具有更大的线性复杂度以及更多的序列个数。在本文中，将进一步推广Udaya和Siddiqi的工作，构造出一类新的一般Galois环上的GMW序列，并对其线性复杂度进行研究。结果表明，构造得到的这类GMW序列仍然具有非常大的线性复杂度。收稿日期：2007-01-05；修回日期：2008-01-05基金项目：国家自然科学基金资助项目（60373041,90104034）FoundationItem:TheNationalNaturalScienceFoundationofChina(60373041,90104034)本文中假设p为任意素数，

7、e,r,u为任意正整数。用表示具有特征pe及阶per的Galois环，用R’表示具有特征pe及阶peru的Galois环。R中所有的可逆元组成了一个乘法群，记为。同样地，把中所有的可逆元所组成的群记为。可以表示成它的2个乘法子群的直积，即，其中是阶为的循环群，是阶为第3期孙霓刚等：Galois环上的一类GMW序列及其线性复杂度·25·的子群并且其每个元素的阶均整除。中任意元素均可以表示成=，其中，。用表示从到的迹函数，表示从到整数剩余类环的迹函数。有关Galois环的内容请参见文献[10,11]。2环上GMW序列本节中将构造一类Galois环上的GM

8、W序列。2.1R上的置换假设b为任意正整数且满足，。对于中任意元素＝，其中，定义映射：满足引理1是上的置换。