legendre序列在gf(p)上的线性复杂度

《legendre序列在gf(p)上的线性复杂度》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3期何贤芒：Legendre序列在GF(p)上的线性复杂度·21·Legendre序列在GF(p)上的线性复杂度何贤芒(复旦大学计算机与信息技术系，上海200433)摘要：线性复杂度是度量流密码安全性的一个重要指标。GF(2)上序列可以把它看成GF(p)上的序列，因此需要研究序列在GF(p)(p是较小的奇素数)上的线性复杂度。从这个观点出发，讨论了Legendre序列在GF(p)上的线性复杂度，在应用部分发现了Legendre序列在分圆多项式分解上一个应用，并对此做了一些扩展。关键词：Legendre序列；线性复杂度；分圆

2、多项式；二次剩余中图分类号：TP309.7文献标识码：A文章编号：1000-436X(2008)03-0016-07OntheGF(p)linearcomplexityoflegendresequenceHEXian-mang(DepartmentofComputingandInformationTechnology,FudanUniversity,Shanghai200433,China)Abstract:Linearcomplexityisanimportantcryptographiccriterionofstream

3、ciphers.ThesequencesoverGF(2)canbeconsideredassequencesoverGF(p)(pisasmalloddprimenumber),therefore,theirlinearcomplexityneedstobestudiedoverGF(p).Fromthisperspective,thelinearcomplexityoflegendresequenceoverGF(p)wasdiscussed.Itsapplicationoncyclotomicpolynomialfac

4、toringandsomeextensionsarealsocovered.Keywords:Legendresequence;linearcomplexity;cyclotomicpolynomial;quadraticresidue第3期何贤芒：Legendre序列在GF(p)上的线性复杂度·21·1引言线性复杂度是衡量流密码安全性重要指标之一。序列的线性复杂度即为产生该序列的最短线性移位寄存器的级数。序列除了好的伪随机性外，必须有较高的线性复杂度。只要已知序列线性复杂度的2倍个连续元素就可以用BM算法或者通过解线性方程

5、组来找到序列所满足的线性递归关系，进而确定出整个序列，因此，线性复杂度是度量流密码强度的一个重要指标。A.Klapper[1]指出:对于二元周期序列，它在GF(2)上线性复杂度具有高的线性复杂度是不够的，可以把二元周期序列看成为GF(p)(p是较小的奇素数)上序列，只不过这个序列只有GF(p)上的元素0、1，而没有其他元素而已。为了密码学应用的目的，必须考虑序列在GF(p)上的线性复杂度，如果二元周期序列在GF(p)上的线性复杂度很低，这类序列同样是不安全的，同时指出某些由Chan和Games构造的几何序列[2]，它们在GF

6、(2)上有较高的线性复杂度，但是在GF(p)上有低的线性复杂度。从这个观点出发，需要研究一些序列在GF(p)上的线性复杂度。收稿日期：2006-12-25；修回日期：2007-12-27Legendre序列是一类十分重要的序列，关于它的各种性质都已经研究比较透彻了。它有着较高的线性复杂度，较好的自相关性，伪随机性能优越(见文献[3])。R.Turyn在文献[4]中给出了Legendre序列的极小多项式，丁存生等在文献[5]中给出了周期为N的Legendre序列的在GF(2)上线性复杂度和极小多项式最具体的结果如下：第3期何贤

7、芒：Legendre序列在GF(p)上的线性复杂度·21·周期为N序列的自相关性如下定义：，Legendre序列有较好的自相关性，周期为N的Legendre序列自相关性()性质如下：Jeong-HeonKim等在文献[6]中给出了Legendre序列的迹(trace)表示的一般结果。鉴于A.Klapper在文献[1]中提出的上述观点，本文主要讨论Legendre序列的在GF(p)上的线性复杂度，在应用部分发现了Legendre序列在分圆多项式分解上一个应用，并对此做了扩展。2准备工作设N是个奇素数，Legendre序列定义如

8、下：对每个是Legendre符号。为了方便讨论，本文中做如下的符号表示：N是奇素数，是Legendre序列的周期，由分圆多项式的理论知道，当N是素数时，，，β是域上的次本原根（m=，设是次本原根，那么就是次本原根），是模的二次剩余集合，是模的非二次剩余集合，，下面的引理1、2和3出自于文献