ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

An algorithm for computing all the critical points of exponent periodic sequences

  • 1.

    Department of Applied Mathematics, Anhui Agricultural University, Hefei 230036, China

  • 2.

    School of Mathematics and Physics, Anhui Jianzhu University, Hefei 230601, China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2018.02.003
  • Received Date: 24 August 2016
  • Rev Recd Date: 22 November 2017
  • Publish Date: 28 February 2018
    Abstract

  • Abstract

    The k-error linear complexity of periodic sequences is an important security indice of stream cipher systems. The k-error linear complexity decreases as the number of errors k increases, that the critical points are those where a decrease occurs in the k-error linear complexity. The pn periodic sequences over the finite field GF(pm) were focused upon， where p is a prime. Some properties of the k-error linear complexity were discussed, and an algorithm was presented for computing all the critical points for a given sequence.

    Abstract

    The k-error linear complexity of periodic sequences is an important security indice of stream cipher systems. The k-error linear complexity decreases as the number of errors k increases, that the critical points are those where a decrease occurs in the k-error linear complexity. The pn periodic sequences over the finite field GF(pm) were focused upon， where p is a prime. Some properties of the k-error linear complexity were discussed, and an algorithm was presented for computing all the critical points for a given sequence.
    • FullText(HTML)
  • loading
    • References(15)
  • [1]
    GAMES R A, CHAN A H. A fast algorithm for determining the linear complexity of a binary sequence with period 2n[J]. IEEE Transactions on Information Theory, 1983, 29(1): 144-146.
    [2]
    DING C S, XIAO G Z, SHANW J. The Stability Theory of Stream Ciphers[M]. Berlin: Springer-Verlag, 1991: Chapter 5.
    [3]
    STAMP M, MARTIN C F. An algorithm for the k-error linear complexity of binary sequences with period 2n[J]. IEEE Transactions on Information Theory, 1993, 39(4): 1398-1401.
    [4]
    KAIDA T, UEHARA S, IMAMURA K. An algorithm for the k-error linear complexity of sequences over GF(pm) with period pn, p a prime[J]. Information and Computation, 1999, 151(2): 134-147.
    [5]
    LAUDER A G B, PATERSON K G. Computing the error linear complexity spectrum of a binary sequence of period 2n[J]. IEEE Transactions on Information Theory, 2003, 49(1): 273-280.
    [6]
    KAIDA T.On the generalized Lauder-Paterson algorithm and profiles of the k-error linear complexity for exponent periodic sequences[C]// Sequences and Their Applications - SETA 2004. Heidelberg: Springer, 2005, LNCS 3486: 166-178.
    [7]
    KURSOSAWA K, SATO F,SAKATA T, et al. A relationship between linear complexity and k-error linear complexity[J]. IEEE Transactions on Information Theory, 2000, 46(2): 694-698.
    [8]
    赵耀东, 戚文峰. 二元周期序列的k错误线性复杂度[J]. 电子学报, 2005, 33(1): 12-16.
    ZHAO Yaodong, QI Wenfeng. On the k-error linear complexity of binary period sequences[J]. Acta Electronica Sinica, 2005, 33(1): 12-16.
    [9]
    MEIDL W, NIEDERREITER H. On the expected value of the linear complexity and k-error linear complexity of periodic sequences[J]. IEEE Transactions on Information Theory, 2002, 48(11): 2817-2825.
    [10]
    MEIDL W, VENKATESWARLU A. Remarks on the k-error linear complexity of pn-periodic sequences[J]. Designs, Codes and Cryptography, 2007, 42(2): 181-193.
    [11]
    朱凤翔, 戚文峰.Fp上pn-周期序列的1-错线性复杂度[J]. 电子与信息学报, 2007, 29(9): 2222-2225.
    ZHU Fengxiang, QI Wenfeng. 1-error linear complexity of pn-periodic sequences over Fp[J]. Journal of Electronics & Information Technology, 2007, 29(9): 2222-2225.
    [12]
    李鹤龄, 戚文峰.Fp上pn-周期序列的k-错线性复杂度[J]. 通信学报, 2010, 31(6): 19-24.
    LI Heling, QI Wenfeng. k-error sequences of pn-periodic sequences over Fp[J]. Journal on Communications, 2010, 31(6): 19-24.
    [13]
    CHANG Z L, KE P H. On the error linear complexity spectrum of binary sequences with period of power of two[J]. Chinese Journal of Electronics, 2015, 24(2): 366-372.
    [14]
    TANG Miao. An algorithm for computing the error sequence of pn-periodic binary sequences[J]. Applicable Algebra in Engineering, Communication and Computing, 2014, 25(3): 197-212.
    [15]
    唐淼, 开晓山. 三元3n周期序列的k错线性复杂度的性质[J]. 中国科学技术大学学报, 2015, 45(2): 107-111, 116.
    TANG Miao, KAI Xiaoshan. Some properties of the k-error linear complexity of ternary 3n-periodic sequences[J]. Journal of University of Science and Technology of China, 2015, 45(2): 107-111, 116.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    GAMES R A, CHAN A H. A fast algorithm for determining the linear complexity of a binary sequence with period 2n[J]. IEEE Transactions on Information Theory, 1983, 29(1): 144-146.
    [2]
    DING C S, XIAO G Z, SHANW J. The Stability Theory of Stream Ciphers[M]. Berlin: Springer-Verlag, 1991: Chapter 5.
    [3]
    STAMP M, MARTIN C F. An algorithm for the k-error linear complexity of binary sequences with period 2n[J]. IEEE Transactions on Information Theory, 1993, 39(4): 1398-1401.
    [4]
    KAIDA T, UEHARA S, IMAMURA K. An algorithm for the k-error linear complexity of sequences over GF(pm) with period pn, p a prime[J]. Information and Computation, 1999, 151(2): 134-147.
    [5]
    LAUDER A G B, PATERSON K G. Computing the error linear complexity spectrum of a binary sequence of period 2n[J]. IEEE Transactions on Information Theory, 2003, 49(1): 273-280.
    [6]
    KAIDA T.On the generalized Lauder-Paterson algorithm and profiles of the k-error linear complexity for exponent periodic sequences[C]// Sequences and Their Applications - SETA 2004. Heidelberg: Springer, 2005, LNCS 3486: 166-178.
    [7]
    KURSOSAWA K, SATO F,SAKATA T, et al. A relationship between linear complexity and k-error linear complexity[J]. IEEE Transactions on Information Theory, 2000, 46(2): 694-698.
    [8]
    赵耀东, 戚文峰. 二元周期序列的k错误线性复杂度[J]. 电子学报, 2005, 33(1): 12-16.
    ZHAO Yaodong, QI Wenfeng. On the k-error linear complexity of binary period sequences[J]. Acta Electronica Sinica, 2005, 33(1): 12-16.
    [9]
    MEIDL W, NIEDERREITER H. On the expected value of the linear complexity and k-error linear complexity of periodic sequences[J]. IEEE Transactions on Information Theory, 2002, 48(11): 2817-2825.
    [10]
    MEIDL W, VENKATESWARLU A. Remarks on the k-error linear complexity of pn-periodic sequences[J]. Designs, Codes and Cryptography, 2007, 42(2): 181-193.
    [11]
    朱凤翔, 戚文峰.Fp上pn-周期序列的1-错线性复杂度[J]. 电子与信息学报, 2007, 29(9): 2222-2225.
    ZHU Fengxiang, QI Wenfeng. 1-error linear complexity of pn-periodic sequences over Fp[J]. Journal of Electronics & Information Technology, 2007, 29(9): 2222-2225.
    [12]
    李鹤龄, 戚文峰.Fp上pn-周期序列的k-错线性复杂度[J]. 通信学报, 2010, 31(6): 19-24.
    LI Heling, QI Wenfeng. k-error sequences of pn-periodic sequences over Fp[J]. Journal on Communications, 2010, 31(6): 19-24.
    [13]
    CHANG Z L, KE P H. On the error linear complexity spectrum of binary sequences with period of power of two[J]. Chinese Journal of Electronics, 2015, 24(2): 366-372.
    [14]
    TANG Miao. An algorithm for computing the error sequence of pn-periodic binary sequences[J]. Applicable Algebra in Engineering, Communication and Computing, 2014, 25(3): 197-212.
    [15]
    唐淼, 开晓山. 三元3n周期序列的k错线性复杂度的性质[J]. 中国科学技术大学学报, 2015, 45(2): 107-111, 116.
    TANG Miao, KAI Xiaoshan. Some properties of the k-error linear complexity of ternary 3n-periodic sequences[J]. Journal of University of Science and Technology of China, 2015, 45(2): 107-111, 116.
    Recommended articles
    TrendMD
    Volume 48 Issue 2 page: 105-110
    Cover

    Article Metrics

    Article views (517) PDF downloads(209)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return