Search Advanced

AIMS Mathematics

2022, Volume 7, Issue 8: 13790-13802. doi: 10.3934/math.2022760
Previous Article Next Article
Research article

Linear complexity and 2-adic complexity of binary interleaved sequences with optimal autocorrelation magnitude

  • 1.
    School of Science, Xi'an University of Architecture and Technology, Xi'an 710055, China
  • 2.
    School of Science, Chang'an University, Xi'an 710064, China
  • Received: 28 February 2022 Revised: 03 May 2022 Accepted: 10 May 2022 Published: 23 May 2022

  • MSC : 94A60, 11T22

  • A construction of binary sequences with period $ 4N $ and optimal autocorrelation magnitude has been investigated based on sampling and interleaving technique. We determine the exact value of the linear complexity of the constructed sequences according to the deep relationship among the characteristic polynomials, and show it is $ 2N+2 $. Moreover, we determine the 2-adic complexity of these sequences by the autocorrelation function, and show it can attain the maximum value. Results show that such sequences can resist both the Berlekamp-Massey attack and the Rational Approximation Algorithm, in addition are good for communication.

    Citation: Yan Wang, Ying Cao, Ziling Heng, Weiqiong Wang. Linear complexity and 2-adic complexity of binary interleaved sequences with optimal autocorrelation magnitude[J]. AIMS Mathematics, 2022, 7(8): 13790-13802. doi: 10.3934/math.2022760

    Related Papers:

  • A construction of binary sequences with period $ 4N $ and optimal autocorrelation magnitude has been investigated based on sampling and interleaving technique. We determine the exact value of the linear complexity of the constructed sequences according to the deep relationship among the characteristic polynomials, and show it is $ 2N+2 $. Moreover, we determine the 2-adic complexity of these sequences by the autocorrelation function, and show it can attain the maximum value. Results show that such sequences can resist both the Berlekamp-Massey attack and the Rational Approximation Algorithm, in addition are good for communication.


    加载中


    [1] T. W. Cusick, C. Ding, A. Renvall, Stream ciphers and number theory, Amsterdam: Elsevier, 2004.
    [2] G. Guang, Theory and applications of $q$-ary interleaved sequences, IEEE T. Inform. Theory, 41 (1995), 400–411. https://doi.org/10.1109/18.370141 doi: 10.1109/18.370141
    [3] S. W. Golomb, G. Gong, Signal design for good correlation: For wireless communication, cryptography, and radar, Cambridge: Cambridge University Press, 2005.
    [4] Q. Wang, X. Du, The linear complexity of binary sequences with optimal autocorrelation, IEEE T. Inform. Theory, 56 (2010), 6388–6397. https://doi.org/10.1109/TIT.2010.2079550 doi: 10.1109/TIT.2010.2079550
    [5] N. Li, X. Tang, On the linear complexity of binary sequences of period $4N$ with optimal autocorrelation value/magnitude, IEEE T. Inform. Theory, 57 (2011), 7597–7604. https://doi.org/10.1109/TIT.2011.2159575 doi: 10.1109/TIT.2011.2159575
    [6] V. Edemskiy, On the linear complexity of interleaved binary sequences of period $4p$ obtained from Hall sequences or Legendre and Hall sequences, Electron. Lett., 50 (2014), 604–605. https://doi.org/10.1049/el.2014.0568 doi: 10.1049/el.2014.0568
    [7] C. Fan, The linear complexity of a class of binary sequences with optimal autocorrelation, Design. Code. Cryptogr., 86 (2018), 2441–2450. https://doi.org/10.1007/s10623-018-0456-7 doi: 10.1007/s10623-018-0456-7
    [8] S. Zhang, T. Yan, Y. Sun, L. Wang, Linear complexity of two classes of binary interleaved sequences with low autocorrelation, Int. J. Netw. Secur., 22 (2020), 150–154.
    [9] Q. Liu, S. Qiang, M. Yang, K. Feng, Linear complexity of binary interleaved sequences of period $4n$, arXiv preprint, 2021. https://doi.org/10.48550/arXiv.2105.13777
    [10] T. Tian, W. F. Qi, $2$-Adic complexity of binary $m$-sequences, IEEE T. Inform. Theory, 56 (2009), 450–454. https://doi.org/10.1109/TIT.2009.2034904 doi: 10.1109/TIT.2009.2034904
    [11] H. Xiong, L. Qu, C. Li, A new method to compute the 2-adic complexity of binary sequences, IEEE T. Inform. Theory, 60 (2014), 2399–2406. https://doi.org/10.1109/TIT.2014.2304451 doi: 10.1109/TIT.2014.2304451
    [12] H. Hu, Comments on "a new method to compute the 2-adic complexity of binary sequences", IEEE T. Inform. Theory, 60 (2014), 5803–5804. https://doi.org/10.1109/TIT.2014.2336843 doi: 10.1109/TIT.2014.2336843
    [13] Y. Sun, T. Yan, Z. Chen, L. Wang, The 2-adic complexity of a class of binary sequences with optimal autocorrelation magnitude, Cryptogr. Commun., 12 (2020), 675–683. https://doi.org/10.1007/s12095-019-00411-4 doi: 10.1007/s12095-019-00411-4
    [14] M. Yang, L. Zhang, K. Feng, On the 2-adic complexity of a class of binary sequences of period $4p$ with optimal autocorrelation magnitude, 2020 IEEE Int. Sym. Inform. Theory, 2020, 2915–2920. https://doi.org/10.1109/ISIT44484.2020.9174142 doi: 10.1109/ISIT44484.2020.9174142
    [15] Y. Sun, T. Yan, Q. Wang, The 2-adic complexity of Yu-Gong sequences with interleaved structure and optimal autocorrelation magnitude, Design. Code. Cryptogr., 89 (2021), 695–707. https://doi.org/10.1007/s10623-020-00841-9 doi: 10.1007/s10623-020-00841-9
    [16] L. Zhang, J. Zhang, M. Yang, K. Feng, On the 2-adic complexity of the Ding-Helleseth-Martinsen binary sequences, IEEE T. Inform. Theory, 66 (2020), 4613–4620. https://doi.org/10.1109/TIT.2020.2964171 doi: 10.1109/TIT.2020.2964171
    [17] S. Qiang, X. Jing, M. Yang, The 2-adic complexity of two classes of binary sequences with interleaved structure, arXiv preprint, 2020. https://doi.org/10.48550/arXiv.2011.12080
    [18] Z. Xiao, X. Zeng, 2-Adic complexity of two constructions of binary sequences with period $4N$ and optimal autocorrelation magnitude, Cryptogr. Commun., 13 (2021), 865–885. https://doi.org/10.1007/s12095-021-00498-8 doi: 10.1007/s12095-021-00498-8
    [19] X. Tang, G. Gong, New constructions of binary sequences with optimal autocorrelation value/magnitude, IEEE T. Inform. Theory, 56 (2010), 1278–1286. https://doi.org/10.1109/TIT.2009.2039159 doi: 10.1109/TIT.2009.2039159
    [20] V. Edemskiy, Y. Sun, The symmetric 2-adic complexity of sequences with optimal autocorrelation magnitude and length $8q$, Cryptogr. Commun., 14 (2021), 183–199. https://doi.org/10.1007/s12095-021-00503-0 doi: 10.1007/s12095-021-00503-0
    [21] X. Tang, C. Ding, New classes of balanced quaternary and almost balanced binary sequences with optimal autocorrelation value, IEEE T. Inform. Theory, 56 (2010), 6398–6405. https://doi.org/10.1109/TIT.2010.2081170 doi: 10.1109/TIT.2010.2081170
    [22] W. Su, Y. Yang, C. Fan, New optimal binary sequences with period $4p$ via interleaving Ding-Helleseth-Lam sequences, Design. Code. Cryptogr., 86 (2018), 1329–1338. https://doi.org/10.1007/s10623-017-0398-5 doi: 10.1007/s10623-017-0398-5
    [23] J. Wang, Structure and properties of binary and quaternary sequence analysis, Huaibei Normal Univ., 2021.
  • Reader Comments
  • © 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
AIMS Mathematics
1.8 3.4

Metrics

Article views(1485) PDF downloads(88) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(1)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog