A brief view on the linear and 2-adic complexities of pseudorandom binary sequences

Hezheng Lin; Lingmei Xiao; Zhixiong Chen; Hezheng Lin; Lingmei Xiao; Zhixiong Chen

doi:10.3934/math.2026823

AIMS Mathematics

2026, Volume 11, Issue 7: 20267-20290. doi: 10.3934/math.2026823

Previous Article Next Article

Review Topical Sections

A brief view on the linear and 2-adic complexities of pseudorandom binary sequences

1.
Fujian Key Laboratory of Financial Information Processing, Putian University, Putian, Fujian 351100, China
2.
Key Laboratory of Applied Mathematics of Fujian Province University, Putian University, Putian, Fujian 351100, China

Received: 03 March 2026 Revised: 13 June 2026 Accepted: 24 June 2026 Published: 09 July 2026
MSC : 94A60

In this survey, we review pseudorandom binary sequences generated by linear feedback shift registers (LFSRs) and feedback with carry shift registers (FCSRs), respectively. A natural question is how to determine the size of a register (LFSR or FCSR) that generates a given sequence. It can be transferred mathematically in terms of the theory of formal power series for LFSRs and of $ 2 $-adic integers for FCSRs, respectively. Hence, the linear complexity (resp. $ 2 $-adic complexity) of an eventually periodic sequence is determined by its rational formal power series (resp. rational $ 2 $-adic integer). The $ N $th linear complexity (resp. $ N $th $ 2 $-adic complexity) of a sequence of length $ N $ is the minimal linear complexity (resp. $ 2 $-adic complexity) of all eventually periodic sequences which start with the $ N $-length sequence. We present results on the average and asymptotic behavior of finite length and periodic sequences. We also present bounds on the $ N $th linear complexity (resp. $ N $th $ 2 $-adic complexity) for algebraic sequences which are non-eventually periodic. Our primary goal is to assist cryptographic novices in gaining a better understanding and mastery of the design and analysis of shift register sequences.
- stream cipher,
- binary sequence,
- linear complexity,
- 2-adic complexity
Citation: Hezheng Lin, Lingmei Xiao, Zhixiong Chen. A brief view on the linear and 2-adic complexities of pseudorandom binary sequences[J]. AIMS Mathematics, 2026, 11(7): 20267-20290. doi: 10.3934/math.2026823

Related Papers:

Abstract

In this survey, we review pseudorandom binary sequences generated by linear feedback shift registers (LFSRs) and feedback with carry shift registers (FCSRs), respectively. A natural question is how to determine the size of a register (LFSR or FCSR) that generates a given sequence. It can be transferred mathematically in terms of the theory of formal power series for LFSRs and of $ 2 $-adic integers for FCSRs, respectively. Hence, the linear complexity (resp. $ 2 $-adic complexity) of an eventually periodic sequence is determined by its rational formal power series (resp. rational $ 2 $-adic integer). The $ N $th linear complexity (resp. $ N $th $ 2 $-adic complexity) of a sequence of length $ N $ is the minimal linear complexity (resp. $ 2 $-adic complexity) of all eventually periodic sequences which start with the $ N $-length sequence. We present results on the average and asymptotic behavior of finite length and periodic sequences. We also present bounds on the $ N $th linear complexity (resp. $ N $th $ 2 $-adic complexity) for algebraic sequences which are non-eventually periodic. Our primary goal is to assist cryptographic novices in gaining a better understanding and mastery of the design and analysis of shift register sequences.

References

[1]	J. P. Allouche, J. Shallit, Automatic sequences: Theory, applications, generalizations, Cambridge University Press, 2003. https://doi.org/10.1017/CBO9780511546563
[2]	S. W. Golomb, G. Gong, Signal design for good correlation - for wireless communication, cryptography and radar, Cambridge University Press, 2005. https://doi.org/10.1017/CBO9780511546907
[3]	M. Goresky, A. Klapper, Algebraic shift register sequences, Cambridge University Press, 2012. https://doi.org/10.1017/CBO9781139057448
[4]	C. L. Li, A survey on complexity measures for pseudo-random sequences, Cryptography, 8 (2024), 25. http://dx.doi.org/10.3390/cryptography8020025 doi: 10.3390/cryptography8020025
[5]	Z. X. Chen, Trace representation and linear complexity of binary sequences derived from Fermat quotients, Sci. China Inf. Sci., 57 (2014), 1–10. http://dx.doi.org/10.1007/s11432-014-5092-x doi: 10.1007/s11432-014-5092-x
[6]	Z. X. Chen, X. N. Du, R. Marzouk, Trace representation of pseudorandom binary sequences derived from Euler quotients, Appl. Algebra Eng. Commun. Comput., 26 (2015), 555–570. http://dx.doi.org/10.1007/s00200-015-0265-4 doi: 10.1007/s00200-015-0265-4
[7]	J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, 15 (1969), 122–127. http://dx.doi.org/10.1109/tit.1969.1054260 doi: 10.1109/tit.1969.1054260
[8]	R. A. Rueppel, Analysis and design of stream ciphers, Berlin, Heidelberg: Springer, 2012. https://doi.org/10.1007/978-3-642-82865-2
[9]	H. Niederreiter, The probabilistic theory of linear complexity, In: Advances in cryptology - EUROCRYPT' 88, 330 (1988), 191–209. https://doi.org/10.1007/3-540-45961-8_17
[10]	H. Niederreiter, A combinatorial approach to probabilistic results on the linear complexity profile of random sequences, J. Cryptol., 2 (1990), 105–112. http://dx.doi.org/10.1007/bf00204450 doi: 10.1007/bf00204450
[11]	M. Z. Wang, J. L. Massey, The characterization of all binary sequences with perfect linear complexity profiles, In: Workshop on the theory and application of cryptographic techniques - EUROCRYPT' 86, 1986, 35–36.
[12]	L. Mérai, A. Winterhof, Pseudorandom sequences derived from automatic sequences, Cryptogr. Commun., 14 (2022), 783–815. http://dx.doi.org/10.1007/s12095-022-00556-9 doi: 10.1007/s12095-022-00556-9
[13]	J. P. Allouche, G. N. Han, H. Niederreiter, Perfect linear complexity profile and apwenian sequences, Finite Fields Appl., 68 (2020), 101761. http://dx.doi.org/10.1016/j.ffa.2020.101761 doi: 10.1016/j.ffa.2020.101761
[14]	H. Niederreiter, Sequences with almost perfect linear complexity profile, In: Advances in cryptology — EUROCRYPT' 87, 304 (1987), 37–51. https://doi.org/10.1007/3-540-39118-5_5
[15]	J. Grünberger, Linear complexity and continued fractions of families of binary sequences, Master Thesis, Johannes Kepler University Linz, 2024.
[16]	H. Niederreiter, Linear complexity and related complexity measures for sequences, In: Progress in cryptology - INDOCRYPT 2003, 2904 (2003), 1–17. http://dx.doi.org/10.1007/978-3-540-24582-7_1
[17]	H. Niederreiter, C. P. Xing, Rational points on curves over finite fields: Theory and applications, Cambridge University Press, 2001. http://dx.doi.org/10.1017/CBO9781107325951.003
[18]	C. P. Xing, K. Y. Lam, Sequences with almost perfect linear complexity profiles and curves over finite fields, IEEE Trans. Inf. Theory, 45 (1999), 1267–1270. http://dx.doi.org/10.1109/18.761282 doi: 10.1109/18.761282
[19]	W. Meidl, H. Niederreiter, On the expected value of the linear complexity and the $k$-error linear complexity of periodic sequences, IEEE Trans. Inf. Theory, 48 (2002), 2817–2825. http://dx.doi.org/10.1109/tit.2002.804050 doi: 10.1109/tit.2002.804050
[20]	B. Kjos-Hanssen, On the complexity of automatic complexity, Theory Comput. Syst., 61 (2017), 1427–1439. http://dx.doi.org/10.1007/s00224-017-9795-4 doi: 10.1007/s00224-017-9795-4
[21]	B. Kjos-Hanssen, Automatic complexity of shift register sequences, Discrete Math., 341 (2018), 2409–2417. http://dx.doi.org/10.1016/j.disc.2018.05.015 doi: 10.1016/j.disc.2018.05.015
[22]	H. Zantema, W. Bosma, Complexity of automatic sequences, Inf. Comput., 288 (2022), 104710. http://dx.doi.org/10.1016/j.ic.2021.104710 doi: 10.1016/j.ic.2021.104710
[23]	L. Mérai, A. Winterhof, On the pseudorandomness of automatic sequences, Cryptogr. Commun., 10 (2018), 1013–1022. http://dx.doi.org/10.1007/s12095-017-0260-7 doi: 10.1007/s12095-017-0260-7
[24]	L. Mérai, A. Winterhof, On the $N$th linear complexity of automatic sequences, J. Number Theory, 187 (2018), 415–429. http://dx.doi.org/10.1016/j.jnt.2017.11.008 doi: 10.1016/j.jnt.2017.11.008
[25]	C. Diem, On the use of expansion series for stream ciphers, LMS J. Comput. Math., 15 (2012), 326–340. http://dx.doi.org/10.1112/s146115701200109x doi: 10.1112/s146115701200109x
[26]	L. Mérai, H. Niederreiter, A. Winterhof, Expansion complexity and linear complexity of sequences over finite fields, Cryptogr. Commun., 9 (2017), 501–509. http://dx.doi.org/10.1007/s12095-016-0189-2 doi: 10.1007/s12095-016-0189-2
[27]	D. Gómez-Pérez, L. Mérai, Algebraic dependence in generating functions and expansion complexity, Adv. Math. Commun., 14 (2020), 307–318. http://dx.doi.org/10.3934/amc.2020022 doi: 10.3934/amc.2020022
[28]	D. Gómez-Pérez, L. Mérai, H. Niederreiter, On the expansion complexity of sequences over finite fields, IEEE Trans. Inf. Theory, 64 (2018), 4228–4232. http://dx.doi.org/10.1109/TIT.2018.2792490 doi: 10.1109/TIT.2018.2792490
[29]	Z. M. Sun, X. Y. Zeng, C. L. Li, Y. Zhang, L. Yi, The expansion complexity of ultimately periodic sequences over finite fields, IEEE Trans. Inf. Theory, 67 (2021), 7550–7560. http://dx.doi.org/10.1109/TIT.2021.3112824 doi: 10.1109/TIT.2021.3112824
[30]	A. Klapper, M. Goresky, Feedback shift registers, 2-adic span, and combiners with memory, J. Cryptol., 10 (1997), 111–147. http://dx.doi.org/10.1007/s001459900024
[31]	Z. R. Chen, Z. X. Chen, J. Obrovsky, A. Winterhof, Maximum-order complexity and $2$-adic complexity, IEEE Trans. Inf. Theory, 70 (2024), 6060–6067. http://dx.doi.org/10.1109/TIT.2024.3405946 doi: 10.1109/TIT.2024.3405946
[32]	J. Obrovsky, $2$-Adic complexity and related measures of pseudorandomness, Master Thesis, Johannes Kepler University Linz, 2023.
[33]	A. Klapper, M. Goresky, Cryptanalysis based on 2-adic rational approximation, In: Advances in cryptology - CRYPTO' 95, 963 (1995), 262–273. http://dx.doi.org/10.1007/3-540-44750-4_21
[34]	A. Klapper, Open problems on with-carry sequence generators, In: Open problems in mathematics and computational science, 2014,181–201. http://dx.doi.org/10.1007/978-3-319-10683-0_9
[35]	T. Tian, W. F. Qi, Expected values for the rational complexity of finite binary sequences, Des. Codes Cryptogr., 55 (2010), 65–79. http://dx.doi.org/10.1007/s10623-009-9331-x doi: 10.1007/s10623-009-9331-x
[36]	A. Winterhof, Pseudorandom binary sequences: Quality measures and number theoretic constructions, IEICE Trans. Fundam., 106 (2023), 1452–1460. https://doi.org/10.1587/transfun.2023SDI0001 doi: 10.1587/transfun.2023SDI0001
[37]	Z. X. Chen, A. Winterhof, Probabilistic results on the $2$-adic complexity, Des. Codes Cryptogr., 93 (2025), 2191–2203. http://dx.doi.org/10.1007/s10623-025-01592-1 doi: 10.1007/s10623-025-01592-1
[38]	H. G. Hu, D. G. Feng, On the $2$-adic complexity and the $k$-error $2$-adic complexity of periodic binary sequences, IEEE Trans. Inf. Theory, 54 (2008), 874–883. http://dx.doi.org/10.1109/TIT.2007.913238 doi: 10.1109/TIT.2007.913238
[39]	Z. X. Chen, A. Winterhof, On the $N$th 2-adic complexity of binary sequences identified with algebraic 2-adic integers, Discrete Appl. Math., 373 (2025), 279–289. http://dx.doi.org/10.1016/j.dam.2025.05.024 doi: 10.1016/j.dam.2025.05.024
[40]	T. Tian, W. F. Qi, $2$-Adic complexity of binary $m$-sequences, IEEE Trans. Inf. Theory, 56 (2009), 450–454. http://dx.doi.org/10.1109/TIT.2009.2034904 doi: 10.1109/TIT.2009.2034904
[41]	C. Seo, S. Lee, Y. Sung, K. Han, S. Kim, A lower bound on the linear span of an FCSR, IEEE Trans. Inf. Theory, 46 (2000), 691–693. http://dx.doi.org/10.1109/18.825844 doi: 10.1109/18.825844
[42]	Z. X. Chen, A. I. Gómez, D. Gómez-Pérez, A. Tirkel, Correlation measure, linear complexity and maximum order complexity for families of binary sequences, Finite Fields Appl., 78 (2022), 101977. http://dx.doi.org/10.1016/j.ffa.2021.101977 doi: 10.1016/j.ffa.2021.101977
[43]	C. J. A. Jansen, Investigations on nonlinear stream cipher systems: Construction and evaluation methods, Ph.D. dissertation, Technical University of Delft, 1989.
[44]	C. J. A. Jansen, The maximum order complexity of sequence ensembles, In: Advances in cryptology - EUROCRYPT'91, 547 (1991), 153–159. http://dx.doi.org/10.1007/3-540-46416-6_13
[45]	C. J. A. Jansen, D. E. Boekee, The shortest feedback shift register that can generate a given sequence, In: Advances in cryptology - CRYPTO'89, 435 (1990), 90–99. http://dx.doi.org/10.1007/0-387-34805-0_10
[46]	S. C. Liang, X. Y. Zeng, Z. B. Xiao, Z. M. Sun, Binary sequences with length $n$ and nonlinear complexity not less than $n/2$, IEEE Trans. Inf. Theory, 69 (2023), 8116–8125. http://dx.doi.org/10.1109/TIT.2023.3316252 doi: 10.1109/TIT.2023.3316252
[47]	P. Rizomiliotis, N. Kalouptsidis, Results on the nonlinear span of binary sequences, IEEE Trans. Inf. Theory, 51 (2005), 1555–1563. http://dx.doi.org/10.1109/isit.2004.1365157 doi: 10.1109/isit.2004.1365157
[48]	Z. M. Sun, X. Y. Zeng, C. L. Li, T. Helleseth, Investigations on periodic sequences with maximum nonlinear complexity, IEEE Trans. Inf. Theory, 63 (2017), 6188–6198. http://dx.doi.org/10.1109/TIT.2017.2714681 doi: 10.1109/TIT.2017.2714681
[49]	A. Klapper, Expected $\pi$-adic security measures of sequences, IEEE Trans. Inf. Theory, 56 (2010), 2486–2501. http://dx.doi.org/10.1109/TIT.2010.2044059 doi: 10.1109/TIT.2010.2044059
[50]	M. Vielhaber, M. P. Canales Chacón, S. Jara Ceballos, Rational complexity of binary sequences, F$\mathbb{Q}$SRs and pseudo-ultrametric continued fractions in $\mathbb{R}$, Cryptogr. Commun., 14 (2022), 433–457. http://dx.doi.org/10.1007/s12095-021-00539-2 doi: 10.1007/s12095-021-00539-2

Reader Comments

Your name:*

Email:*
© 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)