On correlation measures of binary half-ℓ-sequences

i

This article has been updated. A Correction to this article was published on .

i

The Original Article was published on

i

The Original Article was published on

i

This article has been updated

i

This article was retracted on

i

This article has been updated

Abstract

Half-ℓ-sequences as an extension of ℓ-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-ℓ-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.

Keywords

pseudorandom sequences / FCSR / half-ℓ-sequences / arithmetic correlation

CHANGE HISTORY

A Correction to this paper has been published:
https://doi.org

The Retraction Note was updated to reflect reception of statements of disagreement from all authors.

This article has been retracted.Please see the Retraction Notice for more detail:
https://doi.org

References

[1] D. Lassoued, R. Shah, T. Li, Almost periodic and asymptotically almost periodic functions: part I, Adv. Differ. Equations, 47 (2018), 1-19. https://doi.org/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

[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

[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

[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

[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

[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

[9] T. Gu, A. Klapper, Distribution properties of half-ℓ 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-ℓ-sequences, Cryptogr. Commun., 8 (2016), 383-400. https://doi.org/10.1007/s12095-015-0152-7

[11] Q. Wang, C. H. Tan, New bounds on the imbalance of a half-ℓ-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-ℓ-sequences, Int. J. Network Secur., 24 (2022), 444-449. https://doi.org/10.6633/IJNS.202205_24(3).07

[13] Z. Chen, V. Edemskiy, Z. Niu, Y. Sang, Arithmetic correlation of binary half-ℓ-sequences, IET Inf. Secur., 17 (2023), 289-293. https://doi.org/10.1049/ise2.12093

[14] J. Zhang, Z. Niu, L. Xiao, V. Edemskiy, On the maximum order complexity of ℓ-sequences and related sequences, Int. J. Network Secur., 27 (2025), 1139-1145. https://doi.org/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

[16] L. Xiao, V. Edemskiy, Arithmetic autocorrelation of certain binary half-ℓ-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

[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

[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

[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