k-错线性复杂度分布研究
|
摘要
伪随机序列在密码学、通信和计算机等领域有着十分重要的作用.如何评价伪随机序列是序列密码中的重要问题.
S.W.Golomb认为“好”的伪随机序列在周期长、易生成的基础上需满足：元素分布均衡、好的游程分布、理想的自相关特性.随着伪随机序列研究的不断深入,对于密码意义下“好”的伪随机序列提出了新的要求.1969年,Massey提出了Berlekamp-Massey综合算法后,线性复杂度便成为评价序列伪随机性的重要指标.然而,线性复杂度高的序列其安全强度未必高.例如序列(110010111001011100100)∞的线性复杂度和周期都达到最大值21,但这是一条极不安全的序列.若改变该序列每周期中的一个比特,则序列线性复杂度降为3.因此,人们提出了另一个衡量序列伪随机性的重要指标：k-错线性复杂度.
本文主要研究了周期序列k-错线性复杂度分布,包括k-错线性复杂度值、给定k-错线性复杂度的序列计数、k-错线性复杂度均值以及线性复杂度下降点等问题.主要结果如下：
1.对于2n-周期二元序列,当其线性复杂度为2n-1时,计算了该序列2-错(或3-错)线性复杂度的所有可能值以及具有给定2-错(或3-错)线性复杂度序列的条数,由此计算了该序列2-错(或3-错)线性复杂度的均值,即给出了序列2-错(或3-错)线性复杂度的分布情况.
2.讨论了任一2n-周期二元序列2-错线性复杂度的分布,具体计算了该序列2-错线性复杂度的所有可能值以及具有给定2-错线性复杂度序列的条数,进一步给出了2n-周期二元序列2-错线性复杂度的均值.
3.简单讨论了2n-周期二元平衡序列的2-错线性复杂度的分布.
4.给出了Fp上pn-周期序列所有可能的1-错线性复杂度值以及具有给定1-错线性复杂度的序列条数.从而得到了Fp上pn-周期序列1-错线性复杂度均值,更进一步,计算了Fp上pn-周期随机序列k-错线性复杂度均值的界.
5.给出了周期为2pn二元序列线性复杂度的第一下降点的上界,并指出了周期为2p的二元序列在大多数情况下达了到该上界.
6.给出了Fq上周期为2pn序列线性复杂度第一下降点的上界.
7.对分圆多项式Φpq(x)及其因子进行了分析,并给出了周期为pqn二元序列线性复杂度的第一下降点的上界.
Pseudorandom sequences are widely used in cryptography, communication and computation, etc. It is an important issue that how to evaluate the pseudorandom sequences.
S.W.Golomb considered the good pseudorandom sequences should satisfy:the balanceable distribution of elements、fine runs properties and the ideal auto correlation besides long period and easy generation. With the study of stream cipher, more and more new results appeared and the new requirements about good pseudorandom sequences in cryptography were put forward. The linear complexity became an important standard to estimate the pseudorandom properties after Massey provided the Berlekamp-Massey synthesis algorithm in 1969. However, the sequence having a large linear complexity may not be secure enough. For example, the period and the linear complexity of the sequence (110010111001011100100)∞both reach the maximal value 21, however, it is a quite insecure sequence because altering the last bit of each period will reduce the linear complexity of the sequence to be 3. Therefore, another important standard to scale the pseudorandom properties of the sequences is proposed:k-error linear complexity.
In this dissertation, the distribution property of the terror linear complexity is discussed which include the value of k-error linear complexity, the number of the sequences with the given k-error linear complexity, the expected of the k-error linear complexity and the decreasing point of the linear complexity etc. The main results are as follows:
1. For the 2n-periodic binary sequence with linear complexity 2n-1, the possible values for the 2-error(or 3-error) linear complexity and the number of sequences with certain 2-error(or 3-error) linear complexity, moreover, the expected of the 2-error(or 3-error) linear complexity is calculated, that is, the distribution of the 2-error(or 3-error) linear complexity are provided.
2. For a random 2n-periodic binary sequence, the distribution of the 2-error linear complexity is discussed. That is to say, the possible values for the 2-error linear complexity and the number of sequences with certain 2-error linear complexity are established. Moreover, the expected of the 2-error linear complexity for a random 2n-periodic binary sequence is also given.
3. For a random 2n-periodic balanced binary sequence, the distribution of the 2-error linear complexity is discussed simply.
4. For a pn-periodic sequence over Fp, the possible values of the 1-error linear complexity and the number of sequences with certain 1-error linear complexity are established. Then the expected of the 1-error linear complexity for a random pn-periodic sequence over Fp is also given. Moreover, the bounds for the expect value of k-error linear complexity are provided.
5. The upper bound for the first decreasing point of the linear complexity is given for a binary sequence with period 2p". Furthermore, it is showed that the upper bound can be reached for a binary sequence with period 2p in most condition.
6. The upper bound for the first decreasing point of the linear complexity is given for a sequence with period 2p" over Fq.
7. The cyclotomic polynomialΦpq(x) and its factorization are analyzed and the upper bound for the first decreasing point of the linear complexity is given for a binary sequence with period pqn.
S.W.Golomb认为“好”的伪随机序列在周期长、易生成的基础上需满足：元素分布均衡、好的游程分布、理想的自相关特性.随着伪随机序列研究的不断深入,对于密码意义下“好”的伪随机序列提出了新的要求.1969年,Massey提出了Berlekamp-Massey综合算法后,线性复杂度便成为评价序列伪随机性的重要指标.然而,线性复杂度高的序列其安全强度未必高.例如序列(110010111001011100100)∞的线性复杂度和周期都达到最大值21,但这是一条极不安全的序列.若改变该序列每周期中的一个比特,则序列线性复杂度降为3.因此,人们提出了另一个衡量序列伪随机性的重要指标：k-错线性复杂度.
本文主要研究了周期序列k-错线性复杂度分布,包括k-错线性复杂度值、给定k-错线性复杂度的序列计数、k-错线性复杂度均值以及线性复杂度下降点等问题.主要结果如下：
1.对于2n-周期二元序列,当其线性复杂度为2n-1时,计算了该序列2-错(或3-错)线性复杂度的所有可能值以及具有给定2-错(或3-错)线性复杂度序列的条数,由此计算了该序列2-错(或3-错)线性复杂度的均值,即给出了序列2-错(或3-错)线性复杂度的分布情况.
2.讨论了任一2n-周期二元序列2-错线性复杂度的分布,具体计算了该序列2-错线性复杂度的所有可能值以及具有给定2-错线性复杂度序列的条数,进一步给出了2n-周期二元序列2-错线性复杂度的均值.
3.简单讨论了2n-周期二元平衡序列的2-错线性复杂度的分布.
4.给出了Fp上pn-周期序列所有可能的1-错线性复杂度值以及具有给定1-错线性复杂度的序列条数.从而得到了Fp上pn-周期序列1-错线性复杂度均值,更进一步,计算了Fp上pn-周期随机序列k-错线性复杂度均值的界.
5.给出了周期为2pn二元序列线性复杂度的第一下降点的上界,并指出了周期为2p的二元序列在大多数情况下达了到该上界.
6.给出了Fq上周期为2pn序列线性复杂度第一下降点的上界.
7.对分圆多项式Φpq(x)及其因子进行了分析,并给出了周期为pqn二元序列线性复杂度的第一下降点的上界.
Pseudorandom sequences are widely used in cryptography, communication and computation, etc. It is an important issue that how to evaluate the pseudorandom sequences.
S.W.Golomb considered the good pseudorandom sequences should satisfy:the balanceable distribution of elements、fine runs properties and the ideal auto correlation besides long period and easy generation. With the study of stream cipher, more and more new results appeared and the new requirements about good pseudorandom sequences in cryptography were put forward. The linear complexity became an important standard to estimate the pseudorandom properties after Massey provided the Berlekamp-Massey synthesis algorithm in 1969. However, the sequence having a large linear complexity may not be secure enough. For example, the period and the linear complexity of the sequence (110010111001011100100)∞both reach the maximal value 21, however, it is a quite insecure sequence because altering the last bit of each period will reduce the linear complexity of the sequence to be 3. Therefore, another important standard to scale the pseudorandom properties of the sequences is proposed:k-error linear complexity.
In this dissertation, the distribution property of the terror linear complexity is discussed which include the value of k-error linear complexity, the number of the sequences with the given k-error linear complexity, the expected of the k-error linear complexity and the decreasing point of the linear complexity etc. The main results are as follows:
1. For the 2n-periodic binary sequence with linear complexity 2n-1, the possible values for the 2-error(or 3-error) linear complexity and the number of sequences with certain 2-error(or 3-error) linear complexity, moreover, the expected of the 2-error(or 3-error) linear complexity is calculated, that is, the distribution of the 2-error(or 3-error) linear complexity are provided.
2. For a random 2n-periodic binary sequence, the distribution of the 2-error linear complexity is discussed. That is to say, the possible values for the 2-error linear complexity and the number of sequences with certain 2-error linear complexity are established. Moreover, the expected of the 2-error linear complexity for a random 2n-periodic binary sequence is also given.
3. For a random 2n-periodic balanced binary sequence, the distribution of the 2-error linear complexity is discussed simply.
4. For a pn-periodic sequence over Fp, the possible values of the 1-error linear complexity and the number of sequences with certain 1-error linear complexity are established. Then the expected of the 1-error linear complexity for a random pn-periodic sequence over Fp is also given. Moreover, the bounds for the expect value of k-error linear complexity are provided.
5. The upper bound for the first decreasing point of the linear complexity is given for a binary sequence with period 2p". Furthermore, it is showed that the upper bound can be reached for a binary sequence with period 2p in most condition.
6. The upper bound for the first decreasing point of the linear complexity is given for a sequence with period 2p" over Fq.
7. The cyclotomic polynomialΦpq(x) and its factorization are analyzed and the upper bound for the first decreasing point of the linear complexity is given for a binary sequence with period pqn.
引文
[1]Cusick T, Ding C, Renvall A. Stream Ciphers and Number Theory[M]. Elsevier/North-Holland:North-Holland Mathematical Library 55,1988.
[2]S.W.Golomb. Shift Register Seuqences[M]. San Franscisco, CA:Holden-Day,1967. Revised edition:Laguna Hills, CA:Aegean Zark,1982.
[3]Stinson D R. Cryptography:Theory and Practice[M]. Boca Raton:CRC Press,1995.
[4]Schneier B. Applied Cryptography 2nd Edition:Protocols, Algorithms and Souce Code in C[M]. New York:Wiley John & Sons,1996.
[5]丁存生,肖国镇.流密码学及其应用[M].北京：国防工业出版社,1994.
[6]卢开澄.计算机密码学(第2版)[M].北京：清华大学出版社,1998.
[7]肖国镇,梁传甲,王育民.伪随机序列及其应用[M].北京：国防工业出版社,1985.
[8]J.L.Massey. Shift register sysnthesis and BCH decoding[J]. IEEE Trans. Inform. Theory, 1969,15(1):122-127.
[9]R.A.Rueppel. New approaches to stream ciphers[D]. Zurich, Switzerland:Swiss Federal Institute of Technology,1984.
[10]C. Ding, G. Xiao and W. Shan. The Stability Theory of Stream Ciphers[M]. Lecture Notes in computer Science, Springer-Verlag, Berlin,1991, vol.561.
[11]M. Stamp and C. F. Martin. An algorithm for the k-error linear complexity of binary sequences withperiod 2n[J]. IEEE Trans. Inform. Theory,1993,39(4):1398-1401.
[12]陈兰芳,戚文峰.周期为2mpn的二元序列的2-adic复杂度[J].通信学报,2005,26(6)：6-10.
[13]W. Meidl. Extended Games-Chan algorithm for the 2-adic complexity of FCSR-sequences[J]. Theoretical Computer Science,2003,290:2045-2051.
[14]Honggang Hu and Dengguo Feng. On the 2-adic complexity and k-error 2-adic complexity of periodic binary sequences[A]. In Sequences and Their Applications-SETA'04[C]. LNCS 3486, Springer-Verlag, Seoul,2005:185-196.
[15]H.Niederreiter. Some computable complexity measure for binary sequences[A]. In Sequences and Their Applications[C]. London, U.K.:Springer-Verlag,1999:67-68.
[16]H.Niederreiter. Linear complexity and related complexity measures for sequences[A]. In INDOCRYPT 2003[C]. Springer-Verlag, Berlin,2003,2904:1-17.
[17]A. Rukhin, J. Soto, J. Nechvatal, et al. A statistical test suite for random and pseudorandom number enerators for cryptographic applications[EB/OL]. NIST Special Publication 800-22, 2001:14-46. http://csrc.nist.gov/rng/SP800-22b.pdf.
[18]K.Kurosawa, F.Sato, T.Sakata and W.Kishinota. A relationship between linear complexity and k-error linear complexity[J]. IEEE Trans. Inform. Theory,2000,46(3):694-698.
[19]Wilfried Meidl. How many bits have to be changed to decrease the linear complexity?[J]. Design Codes and Cryptography.2004.33(2):109-122.
[20]Zhihua Niu and Guozheng Xiao. Analysis of the linear complexity and its stability for 2pn-periodic binary sequences[J]. IEICE Trans. Foundamentals,2005, E88-A(9): 2412-2418.
[21]牛志华,白恩健,肖国镇。pmqn周期q元序列线性复杂度与k错线性复杂度的关系[J].通信学报,2004.11,25(11)：84-89.
[22]牛志华.周期序列线性复杂度及其稳定性分析[D].西安：电子科技大学,2005.1.
[23]W.Meidl. Linear complexity and k-error linear complexity for pn-periodic sequences[A]. In Coding, Cryptography and ComBinatories, ed. K.Q.Feng, H.Niederreiter and C.P.Xing, Progress in Computer Science and Apllied Logic[C]. Birkhaeuser, Basel,2004,23: 227-235.
[24]赵耀东,戚文峰.二元周期序列的k错误线性复杂度[J].电子学报,2005,33(1)：12-16.
[25]R.A.Rueppel.'Analysis and Design of Stream Ciphers[M]. Berlin, Germany: Springer-Verlag,1986.
[26]H.Niederreiter. The linear complexity profile and the jump complexty of keystream sequences[A]. In Advances in Cryptology-EUROCRYPT'90[C]. Lecture Notes in Computer Science, Berlin, Springer-Verlag,1991,473:174-188.
[27]J.L.Massey and S.Serconek. A fourier transform approach to the linear complexity of nonlinearly filtered sequences[A]. In Advances in Cryptology-CRYPTO'94[C]. Lecture Notes in Computer Science, Y.G.Desmedt Ed., Berlin, Germany:Springer-Verlag,1994,839: 332-340.
[28]J.L.Massey and S.Serconeck. Linear complexity of periodic sequences:a general theory[A]. In Advances in Cryptology-CRYPTO'96[C].Lecture Notes in Computer Science, N.Koblitz Ed., Berlin, Germany:Springer-Verlag,1996,1109:332-340.
[29]Wilfried Meidl.and HaraldNiederreiter. On the expected value of linear complexity and the k-error linear complexity of periodic sequences[J]. IEEE Trans. Inform. Theory,2002, 48(11):2817-2825.
[30]Wilfried Meidl, Harald Niederreiter. Linear complexity, k-error linear complexity, and the discrete fourier transform[J]. Journal of Complexity,2002,18(1):87-103.
[31]Wilfried Meidl. On the stability of 2n-periodic binary sequences[J]. IEEE Trans. Inform. Theory,2005,51(5):1151-1155
[32]H.Niederreiter. Periodic sequences with large k-error linear complexity[J]. IEEE Trans. Inform. Theory,2003.49(2):501-505.
[33]Wilfried Meidl and Harald Niederreiter. Periodic sequences with maximal linear complexity and large k-error linear complexity[J]. Appl.Algebra.Eng.Commun.Comput.,2003,414: 273-286.
[34]Harald Niederreiter and lgor E.Shparlinski. Periodic sequences with maximal linear complexity and almost maximal k-error linear complexity[J]. Cryptography and Coding(K.G.Zaterson, ed.), Springer-Verlag. Berlin, Lecture Notes in Computer Science, 2003,2898:183-189.
[35]胡红钢,冯登国.Fq上具有极大1-error线性复杂度的周期序列[J].软件学报,2005,16(5)：940-945,
[36]胡红钢.几类伪随机序列的研究[D].北京：中国科学院电子学研究所,2005.6.
[37]R.A.Games and A.H.Chan. A fast algorithm for determining the complexity of a bianry sequence with period 2"[J]. IEEE Trans. Inform. Theory,1983,29(1):144-146.
[38]T.Kaida, S.Uehara and K.Imamura. An algorithm for the k-error linear complexity of sequences over GF(pm) with period pn,p a prime[J]. Information and Computation, Academic press, May,1999.151(2):134-147.
[39]Alan G.B Lauder and Kenneth G.Paterson. Computing the error linear complexity spectrum of a binary sequence of period 2n[J]. IEEE Trans. Inform Theory,2003,49(1):273-280.
[40]T.Kaida. On the generalized lauder-paterson algorithm and profiles of the k-error linear complexity for exponent periodic sequences[A]. In Sequences and their Applications'04[C]. Lecture Notes in Computer Sciences.2005,3486:166-178.
[41]陈豪.确定GF(pm)上周期为3n的序列线性复杂度的快速算法[J].中国科学A辑,2006,36(3)：241-247.
[42]Hao Chen. Fast algorithms for determining the linear complexity of sequences over GF(pm) with period 2'n[J]. IEEE Trans. Inform. Theory,2005,51(5):1854-1856.
[43]白恩健,刘晓娟,肖国镇.确定周期为pn的二元序列k-错复杂度曲线的快速算法[J].通信学报,2004,25(10)：1-7.
[44]魏仕民,白国强,肖国镇.确定周期为pn的二元周期序列的线性复杂度的一个快速算法[J].通信学报.1999.20(8)：36-40.
[45]Shimin Wei, Guozhen Xiao and Zhong Chen. A fast algorithm for determining the minimal polynomial of a sequence with period 2pn over GF(q)[J]. IEEE Trans. Inform. Theory,2002, 48(10):2754-2758.
[46]Guozhen Xiao, Shimin Wei, Kwok Yan Lam and Kyoki Imamura. A fast algorithm for determining the linear complexity of a sequence with period pn over GF(q)[J]. IEEE Trans. Inform. Theory,2000,46(6):2203-2206.
[47]魏仕民.确定周期序列k错线性复杂度的一个快速算法[J].电子学报,2004,32(5)：705-708.
[48]魏仕民,肖国镇和陈钟.确定周期为2npm二元序列线性复杂度的快速算法[J].中国科学E辑,2002,32(3)：401-408.
[49]H.Niedereiter and H.Paschinger. Counting functions and expected values in the stability theory of stream ciphers[A]. In Sequences and their Applications[C]. Lecture Notes in Computer Science, Springer, Berlin,1999:318-329,.
[50]Wilfried Meidl and Harald Niederreiter. Counting functions and expected values for the k-error linear complexity[J]. Finite Field and Their Applications 8,2002:142-154.
[51]Hassan Aly and Arne Winterhof. On the k-error linear complexity over Fp of legendre and sidelnikov sequences[J]. Designs. Codes and Cryptography,2006,40(3):369-374.
[52]Yuchang Eun, Hongyeop Song and Gohar M.Kyureghyan. One-error linear complexity over of sidelnikov sequences[A]. In Sequences and their Applications'04[C]. Lecture Notes in Computer Sciences,2005,3486:154-165.
[53]K.Imamura and T.Moriuchi. A fast algorithm for determining the linear complexity of p-ary sequence with period pn,p a prime[J]. IEICE Tech. Rep.1993, IT-93(75):73-78.
[54]柯召,孙琦.数论讲义[M].北京：国防工业出版社,1994.
[55]Lidl R and H.Niederrciter. Finite fields[M]. Reading, MA:Addison-Wesley,1983.
[56]K. H Rosen. Elementary Number Theory and its Applications[M]. Reading, MA: Addison-Wesley,1988.
[57]D.Shanks. Solved and Unsolved Problems in Number Theory,2nd ed.[M]. Chelsea Publishing Company. New York,1978.
[58]A.Migotti. Zur Theorie der Kreisteilungsgleichung. S-B. Der Math.-Naturwiss[M]. Class der Kaiser.Akad. der Wiss. Wien 1883,87:7-14.
[59]M.Beiter. The midterm coefficient of the cyclotomic polynomial Φpq(x)[J]. Amer. Math. Montly 1964,71:769-770.
[60]L.Carlitz. The number of terms in the cyclotomic polynomial Φpq(x)[J]. Amer. Math. Monthly 1966,73:979-981.
[61]T.Y.Lam and K.H.Leung. On the cyclotomic polynomial Φpq(x)[J]. Amer. Math. Monthly 1996,103:562-564.
[2]S.W.Golomb. Shift Register Seuqences[M]. San Franscisco, CA:Holden-Day,1967. Revised edition:Laguna Hills, CA:Aegean Zark,1982.
[3]Stinson D R. Cryptography:Theory and Practice[M]. Boca Raton:CRC Press,1995.
[4]Schneier B. Applied Cryptography 2nd Edition:Protocols, Algorithms and Souce Code in C[M]. New York:Wiley John & Sons,1996.
[5]丁存生,肖国镇.流密码学及其应用[M].北京：国防工业出版社,1994.
[6]卢开澄.计算机密码学(第2版)[M].北京：清华大学出版社,1998.
[7]肖国镇,梁传甲,王育民.伪随机序列及其应用[M].北京：国防工业出版社,1985.
[8]J.L.Massey. Shift register sysnthesis and BCH decoding[J]. IEEE Trans. Inform. Theory, 1969,15(1):122-127.
[9]R.A.Rueppel. New approaches to stream ciphers[D]. Zurich, Switzerland:Swiss Federal Institute of Technology,1984.
[10]C. Ding, G. Xiao and W. Shan. The Stability Theory of Stream Ciphers[M]. Lecture Notes in computer Science, Springer-Verlag, Berlin,1991, vol.561.
[11]M. Stamp and C. F. Martin. An algorithm for the k-error linear complexity of binary sequences withperiod 2n[J]. IEEE Trans. Inform. Theory,1993,39(4):1398-1401.
[12]陈兰芳,戚文峰.周期为2mpn的二元序列的2-adic复杂度[J].通信学报,2005,26(6)：6-10.
[13]W. Meidl. Extended Games-Chan algorithm for the 2-adic complexity of FCSR-sequences[J]. Theoretical Computer Science,2003,290:2045-2051.
[14]Honggang Hu and Dengguo Feng. On the 2-adic complexity and k-error 2-adic complexity of periodic binary sequences[A]. In Sequences and Their Applications-SETA'04[C]. LNCS 3486, Springer-Verlag, Seoul,2005:185-196.
[15]H.Niederreiter. Some computable complexity measure for binary sequences[A]. In Sequences and Their Applications[C]. London, U.K.:Springer-Verlag,1999:67-68.
[16]H.Niederreiter. Linear complexity and related complexity measures for sequences[A]. In INDOCRYPT 2003[C]. Springer-Verlag, Berlin,2003,2904:1-17.
[17]A. Rukhin, J. Soto, J. Nechvatal, et al. A statistical test suite for random and pseudorandom number enerators for cryptographic applications[EB/OL]. NIST Special Publication 800-22, 2001:14-46. http://csrc.nist.gov/rng/SP800-22b.pdf.
[18]K.Kurosawa, F.Sato, T.Sakata and W.Kishinota. A relationship between linear complexity and k-error linear complexity[J]. IEEE Trans. Inform. Theory,2000,46(3):694-698.
[19]Wilfried Meidl. How many bits have to be changed to decrease the linear complexity?[J]. Design Codes and Cryptography.2004.33(2):109-122.
[20]Zhihua Niu and Guozheng Xiao. Analysis of the linear complexity and its stability for 2pn-periodic binary sequences[J]. IEICE Trans. Foundamentals,2005, E88-A(9): 2412-2418.
[21]牛志华,白恩健,肖国镇。pmqn周期q元序列线性复杂度与k错线性复杂度的关系[J].通信学报,2004.11,25(11)：84-89.
[22]牛志华.周期序列线性复杂度及其稳定性分析[D].西安：电子科技大学,2005.1.
[23]W.Meidl. Linear complexity and k-error linear complexity for pn-periodic sequences[A]. In Coding, Cryptography and ComBinatories, ed. K.Q.Feng, H.Niederreiter and C.P.Xing, Progress in Computer Science and Apllied Logic[C]. Birkhaeuser, Basel,2004,23: 227-235.
[24]赵耀东,戚文峰.二元周期序列的k错误线性复杂度[J].电子学报,2005,33(1)：12-16.
[25]R.A.Rueppel.'Analysis and Design of Stream Ciphers[M]. Berlin, Germany: Springer-Verlag,1986.
[26]H.Niederreiter. The linear complexity profile and the jump complexty of keystream sequences[A]. In Advances in Cryptology-EUROCRYPT'90[C]. Lecture Notes in Computer Science, Berlin, Springer-Verlag,1991,473:174-188.
[27]J.L.Massey and S.Serconek. A fourier transform approach to the linear complexity of nonlinearly filtered sequences[A]. In Advances in Cryptology-CRYPTO'94[C]. Lecture Notes in Computer Science, Y.G.Desmedt Ed., Berlin, Germany:Springer-Verlag,1994,839: 332-340.
[28]J.L.Massey and S.Serconeck. Linear complexity of periodic sequences:a general theory[A]. In Advances in Cryptology-CRYPTO'96[C].Lecture Notes in Computer Science, N.Koblitz Ed., Berlin, Germany:Springer-Verlag,1996,1109:332-340.
[29]Wilfried Meidl.and HaraldNiederreiter. On the expected value of linear complexity and the k-error linear complexity of periodic sequences[J]. IEEE Trans. Inform. Theory,2002, 48(11):2817-2825.
[30]Wilfried Meidl, Harald Niederreiter. Linear complexity, k-error linear complexity, and the discrete fourier transform[J]. Journal of Complexity,2002,18(1):87-103.
[31]Wilfried Meidl. On the stability of 2n-periodic binary sequences[J]. IEEE Trans. Inform. Theory,2005,51(5):1151-1155
[32]H.Niederreiter. Periodic sequences with large k-error linear complexity[J]. IEEE Trans. Inform. Theory,2003.49(2):501-505.
[33]Wilfried Meidl and Harald Niederreiter. Periodic sequences with maximal linear complexity and large k-error linear complexity[J]. Appl.Algebra.Eng.Commun.Comput.,2003,414: 273-286.
[34]Harald Niederreiter and lgor E.Shparlinski. Periodic sequences with maximal linear complexity and almost maximal k-error linear complexity[J]. Cryptography and Coding(K.G.Zaterson, ed.), Springer-Verlag. Berlin, Lecture Notes in Computer Science, 2003,2898:183-189.
[35]胡红钢,冯登国.Fq上具有极大1-error线性复杂度的周期序列[J].软件学报,2005,16(5)：940-945,
[36]胡红钢.几类伪随机序列的研究[D].北京：中国科学院电子学研究所,2005.6.
[37]R.A.Games and A.H.Chan. A fast algorithm for determining the complexity of a bianry sequence with period 2"[J]. IEEE Trans. Inform. Theory,1983,29(1):144-146.
[38]T.Kaida, S.Uehara and K.Imamura. An algorithm for the k-error linear complexity of sequences over GF(pm) with period pn,p a prime[J]. Information and Computation, Academic press, May,1999.151(2):134-147.
[39]Alan G.B Lauder and Kenneth G.Paterson. Computing the error linear complexity spectrum of a binary sequence of period 2n[J]. IEEE Trans. Inform Theory,2003,49(1):273-280.
[40]T.Kaida. On the generalized lauder-paterson algorithm and profiles of the k-error linear complexity for exponent periodic sequences[A]. In Sequences and their Applications'04[C]. Lecture Notes in Computer Sciences.2005,3486:166-178.
[41]陈豪.确定GF(pm)上周期为3n的序列线性复杂度的快速算法[J].中国科学A辑,2006,36(3)：241-247.
[42]Hao Chen. Fast algorithms for determining the linear complexity of sequences over GF(pm) with period 2'n[J]. IEEE Trans. Inform. Theory,2005,51(5):1854-1856.
[43]白恩健,刘晓娟,肖国镇.确定周期为pn的二元序列k-错复杂度曲线的快速算法[J].通信学报,2004,25(10)：1-7.
[44]魏仕民,白国强,肖国镇.确定周期为pn的二元周期序列的线性复杂度的一个快速算法[J].通信学报.1999.20(8)：36-40.
[45]Shimin Wei, Guozhen Xiao and Zhong Chen. A fast algorithm for determining the minimal polynomial of a sequence with period 2pn over GF(q)[J]. IEEE Trans. Inform. Theory,2002, 48(10):2754-2758.
[46]Guozhen Xiao, Shimin Wei, Kwok Yan Lam and Kyoki Imamura. A fast algorithm for determining the linear complexity of a sequence with period pn over GF(q)[J]. IEEE Trans. Inform. Theory,2000,46(6):2203-2206.
[47]魏仕民.确定周期序列k错线性复杂度的一个快速算法[J].电子学报,2004,32(5)：705-708.
[48]魏仕民,肖国镇和陈钟.确定周期为2npm二元序列线性复杂度的快速算法[J].中国科学E辑,2002,32(3)：401-408.
[49]H.Niedereiter and H.Paschinger. Counting functions and expected values in the stability theory of stream ciphers[A]. In Sequences and their Applications[C]. Lecture Notes in Computer Science, Springer, Berlin,1999:318-329,.
[50]Wilfried Meidl and Harald Niederreiter. Counting functions and expected values for the k-error linear complexity[J]. Finite Field and Their Applications 8,2002:142-154.
[51]Hassan Aly and Arne Winterhof. On the k-error linear complexity over Fp of legendre and sidelnikov sequences[J]. Designs. Codes and Cryptography,2006,40(3):369-374.
[52]Yuchang Eun, Hongyeop Song and Gohar M.Kyureghyan. One-error linear complexity over of sidelnikov sequences[A]. In Sequences and their Applications'04[C]. Lecture Notes in Computer Sciences,2005,3486:154-165.
[53]K.Imamura and T.Moriuchi. A fast algorithm for determining the linear complexity of p-ary sequence with period pn,p a prime[J]. IEICE Tech. Rep.1993, IT-93(75):73-78.
[54]柯召,孙琦.数论讲义[M].北京：国防工业出版社,1994.
[55]Lidl R and H.Niederrciter. Finite fields[M]. Reading, MA:Addison-Wesley,1983.
[56]K. H Rosen. Elementary Number Theory and its Applications[M]. Reading, MA: Addison-Wesley,1988.
[57]D.Shanks. Solved and Unsolved Problems in Number Theory,2nd ed.[M]. Chelsea Publishing Company. New York,1978.
[58]A.Migotti. Zur Theorie der Kreisteilungsgleichung. S-B. Der Math.-Naturwiss[M]. Class der Kaiser.Akad. der Wiss. Wien 1883,87:7-14.
[59]M.Beiter. The midterm coefficient of the cyclotomic polynomial Φpq(x)[J]. Amer. Math. Montly 1964,71:769-770.
[60]L.Carlitz. The number of terms in the cyclotomic polynomial Φpq(x)[J]. Amer. Math. Monthly 1966,73:979-981.
[61]T.Y.Lam and K.H.Leung. On the cyclotomic polynomial Φpq(x)[J]. Amer. Math. Monthly 1996,103:562-564.