Search Advanced

Electronic Research Archive

2026, Volume 34, Issue 9: 6363-6381. doi: 10.3934/era.2026278
Previous Article Next Article
Research article

On correlation measures of binary half-$ \ell $-sequences

  • 1.
    Fujian Key Laboratory of Financial Information Processing, Putian University, Putian 351100, China
  • 2.
    School of Mathematics and Statistics, Fujian Normal University, Fuzhou 350117, China
  • 3.
    Provincial Key Laboratory of Applied Mathematics, Putian University, Putian 351100, China
  • 4.
    Department of Applied Mathematics and Informatics, Yaroslav-the-Wise Novgorod State University, Veliky Novgorod 173003, Russia
  • Published: 20 July 2026

  • Half-$ \ell $-sequences as an extension of $ \ell $-sequences generated by feedback with carry shift registers (FCSRs) possess desirable pseudorandom properties. In this work, we focus on the arithmetic autocorrelation of binary half-$ \ell $-sequences with connection integers of the form $ q = p_1^{r} p_2^{s} $. For this family of sequences, we establish a tight upper bound on the arithmetic autocorrelation and determine all possible values it can attain, which generalizes earlier results when the connection integer is a prime power. Our statements indicate that such sequences exhibit large arithmetic autocorrelation values yet can also demonstrate almost ideal arithmetic correlations for certain special forms of $ q $. We reveal a profound connection between these values and the class numbers of imaginary quadratic fields. Numerical experiments further validate the theoretical findings.

    Citation: Lingmei Xiao, Feifei Yan, Hezheng Lin, Vladimir Edemskiy. On correlation measures of binary half-$ \ell $-sequences[J]. Electronic Research Archive, 2026, 34(9): 6363-6381. doi: 10.3934/era.2026278

    Related Papers:

  • Half-$ \ell $-sequences as an extension of $ \ell $-sequences generated by feedback with carry shift registers (FCSRs) possess desirable pseudorandom properties. In this work, we focus on the arithmetic autocorrelation of binary half-$ \ell $-sequences with connection integers of the form $ q = p_1^{r} p_2^{s} $. For this family of sequences, we establish a tight upper bound on the arithmetic autocorrelation and determine all possible values it can attain, which generalizes earlier results when the connection integer is a prime power. Our statements indicate that such sequences exhibit large arithmetic autocorrelation values yet can also demonstrate almost ideal arithmetic correlations for certain special forms of $ q $. We reveal a profound connection between these values and the class numbers of imaginary quadratic fields. Numerical experiments further validate the theoretical findings.



    加载中


    [1] D. Lassoued, R. Shah, T. Li, Almost periodic and asymptotically almost periodic functions: part Ⅰ, Adv. Differ. Equations, 47 (2018), 1–19. https://doi.org/10.1186/s13662-018-1487-0 doi: 10.1186/s13662-018-1487-0
    [2] M. Goresky, A. Klapper, Algebraic Shift Register Sequences, Cambridge University Press, 2012.
    [3] A. Klapper, M. Goresky, Feedback shift registers, $2$-adic span, and combiners with memory, J. Cryptol., 10 (1997), 111–147. https://doi.org/10.1007/s001459900024 doi: 10.1007/s001459900024
    [4] M. Goresky, A. Klapper, Arithmetic crosscorrelations of feedback with carry shift register sequences, IEEE Trans. Inf. Theory, 43 (1997), 1342–1345. https://doi.org/10.1109/18.605605 doi: 10.1109/18.605605
    [5] H. Wang, Q. Wen, J. Zhang, GLS: New class of generalized Legendre sequences with optimal arithmetic cross-correlation, RAIRO-Theor. Inf. Appl., 47 (2013), 371–388. https://doi.org/10.1051/ita/2013043 doi: 10.1051/ita/2013043
    [6] Z. Chen, Z. Niu, Y. Sang, C. Wu, Arithmetic autocorrelation of binary $m$-sequences, Cryptologia, 47 (2023), 449–458. https://doi.org/10.1080/01611194.2022.2071116 doi: 10.1080/01611194.2022.2071116
    [7] X. Jing, A. Zhang, K. Feng, Arithmetic autocorrelation distribution of binary $m$-sequences, IEEE Trans. Inf. Theory, 69 (2023), 6040–6047. https://doi.org/10.1109/TIT.2023.3282229 doi: 10.1109/TIT.2023.3282229
    [8] X. Liu, H. Liu, Arithmetic autocorrelation and pattern distribution of binary sequences, Electron. Res. Arch., 33 (2025), 849–866. https://doi.org/10.3934/era.2025038 doi: 10.3934/era.2025038
    [9] T. Gu, A. Klapper, Distribution properties of half-$\ell$ sequences, in Sequences and Their Applications - SETA 2014 (eds. K. U. Schmidt, A. Winterhof), Lecture Notes in Computer Science, 8865 (2014), 234–245. https://doi.org/10.1007/978-3-319-12325-7_20
    [10] T. Gu, A. Klapper, Statistical properties of half-$\ell$-sequences, Cryptogr. Commun., 8 (2016), 383–400. https://doi.org/10.1007/s12095-015-0152-7 doi: 10.1007/s12095-015-0152-7
    [11] Q. Wang, C. H. Tan, New bounds on the imbalance of a half-$\ell$-sequence, in IEEE International Symposium on Information Theory-ISIT 2015, (2015), 2688–2691. https://doi.org/10.1109/ISIT.2015.7282944
    [12] Z. Niu, Y. Sang, On the linear complexity of binary half-$\ell$-sequences, Int. J. Network Secur., 24 (2022), 444–449. https://doi.org/10.6633/IJNS.202205_24(3).07 doi: 10.6633/IJNS.202205_24(3).07
    [13] Z. Chen, V. Edemskiy, Z. Niu, Y. Sang, Arithmetic correlation of binary half-$\ell$-sequences, IET Inf. Secur., 17 (2023), 289–293. https://doi.org/10.1049/ise2.12093 doi: 10.1049/ise2.12093
    [14] J. Zhang, Z. Niu, L. Xiao, V. Edemskiy, On the maximum order complexity of $\ell$-sequences and related sequences, Int. J. Network Secur., 27 (2025), 1139–1145. https://doi.org/10.6633/IJNS.202511_27(6).04 doi: 10.6633/IJNS.202511_27(6).04
    [15] Z. Chen, V. Edemskiy, C. Wu, Binary sequences with ideal and small arithmetic correlations, Cryptogr. Commun., 17 (2025), 453–464. https://doi.org/10.1007/s12095-024-00770-7 doi: 10.1007/s12095-024-00770-7
    [16] L. Xiao, V. Edemskiy, Arithmetic autocorrelation of certain binary half-$\ell$-sequences, in Information Security and Cryptology-Inscrypt 2025, Lecture Notes in Computer Science, 16408 (2026), 388–397. https://doi.org/10.1007/978-981-95-6206-0_20
    [17] K. Ireland, M. Rosen, A Classical Introduction to Modern Number Theory, Graduate Texts in Mathematics, 84, (1990).
    [18] S. Arno, M. L. Robinson, F. S. Wheeler, Imaginary quadratic fields with small odd class number, Acta Arith., 83 (1998), 295–330. https://doi.org/10.4064/aa-83-4-295-330 doi: 10.4064/aa-83-4-295-330
    [19] Z. I. Borevich, I. R. Shefarevich, Number Theory, Academic Press, Orlando, FL, 1966. https://doi.org/10.1201/9781351137621-2
    [20] B. Berndt, Classical theorems on quadratic residues, Enseign. Math., 22 (1976), 261–304.
    [21] P. Ribenboim, Classical Theory of Algebraic Numbers, Springer, New York, 2001.
    [22] A. Shahid, H. L. Huang, M. M. Bhatti, M. Marin, Numerical computation of magnetized bioconvection nanofluid flow with temperature-dependent viscosity and Arrhenius kinetic, Math. Comput. Simul., 200 (2022), 377–392. https://doi.org/10.1016/j.matcom.2022.04.032 doi: 10.1016/j.matcom.2022.04.032
    [23] Y. Cai, C. Ding, Binary sequences with optimal autocorrelation, Theor. Comput. Sci., 410 (2009), 2316–2322. https://doi.org/10.1016/j.tcs.2009.02.021 doi: 10.1016/j.tcs.2009.02.021
    [24] Y. Ren, C. Hou, H. Liu, Correlation properties of interleaved Legendre sequences and Ding-Helleseth-Lam sequences, Electron. Res. Arch., 31 (2023), 4549–4556. https://doi.org/10.3934/era.2023232 doi: 10.3934/era.2023232
  • Reader Comments
  • © 2026 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搜索
Electronic Research Archive
1.2 2.4

Metrics

Article views(72) PDF downloads(6) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(5)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog