pith. sign in

arxiv: 2405.08479 · v4 · submitted 2024-05-14 · 💻 cs.CR

A Survey on Complexity Measures of Pseudo-Random Sequences

Chunlei Li This is my paper

Pith reviewed 2026-05-24 00:42 UTC · model grok-4.3

classification 💻 cs.CR
keywords pseudo-random sequenceslinear complexityquadratic complexitymaximum-order complexityLempel-Ziv complexity2-adic complexityexpansion complexitycorrelation measures
0
0 comments X

The pith

A survey compiles four decades of work on linear, quadratic and maximum-order complexities for pseudo-random sequences and their ties to other measures.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper assembles notable studies on measures that quantify how random-like binary sequences appear. It centers on linear complexity, quadratic complexity and maximum-order complexity while mapping their connections to Lempel-Ziv complexity, expansion complexity, 2-adic complexity and correlation measures. These tools originated after Kolmogorov complexity in the 1960s and serve both theoretical computer science and practical cryptography. A reader cares because the measures determine whether a sequence is predictable enough to compromise security applications.

Core claim

The survey presents the accumulated research on linear, quadratic and maximum-order complexities of pseudo-random sequences together with their established relations to Lempel-Ziv complexity, expansion complexity, 2-adic complexity and correlation measures, thereby tracing the development of randomness-assessment techniques over the last forty years.

What carries the argument

Linear complexity, quadratic complexity and maximum-order complexity, which serve as quantitative tests of the linear predictability and higher-order structure in sequences.

If this is right

  • Relations among the measures allow one complexity value to bound or predict properties of another in sequence design.
  • Developments in any single measure inform the evaluation and construction of sequences used in cryptographic primitives.
  • The reviewed connections to Lempel-Ziv, 2-adic and correlation measures provide multiple independent checks on sequence quality.
  • Ongoing refinement of these measures continues to support both theoretical randomness studies and practical generator construction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Designers of pseudo-random generators could prioritize sequences that score well across several of these measures simultaneously.
  • A unified framework that computes multiple complexities at once might reduce the cost of randomness testing in large-scale applications.
  • The survey's focus suggests that future work could usefully compare these measures against newer statistical tests not covered here.

Load-bearing premise

The papers selected as notable accurately represent the central advancements in these complexity measures without important omissions or selection bias.

What would settle it

Identification of a substantial body of peer-reviewed work from the past four decades on linear, quadratic or maximum-order complexity that is absent from the survey would undermine its coverage claim.

Figures

Figures reproduced from arXiv: 2405.08479 by Chunlei Li.

Figure 1
Figure 1. Figure 1: An m-stage FSR with feedback function f Let Fq be the finite field of q elements, where q is an arbitrary prime power. For a positive integer m, an m-stage feedback shift register (FSR) is a clock-controlled circuit consisting of m consecutive storage units and a 4 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Recursive calculation of the quadratic complexity profile of [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Direct Acyclic Word Graph of s = 110100 [21] With the notions illustrated in Example 1, Jansen in [21] established the following connection between the maximum-order complexity of a sequence s and the depth of DAWG derived from s, and proposed to calculate the maximum-order complexity of s from its DAWG. Proposition 7. Given a sequence s, the maximum-order complexity of s and the depth d(s) of its DAWG sat… view at source ↗
read the original abstract

Since the introduction of the Kolmogorov complexity of binary sequences in the 1960s, there have been significant advancements in the topic of complexity measures for randomness assessment, which are of fundamental importance in theoretical computer science and of practical interest in cryptography. This survey reviews notable research from the past four decades on the linear, quadratic and maximum-order complexities of pseudo-random sequences and their relations with Lempel-Ziv complexity, expansion complexity, 2-adic complexity, and correlation measures.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript is a survey reviewing notable research from the past four decades on linear, quadratic, and maximum-order complexities of pseudo-random sequences, along with their relations to Lempel-Ziv complexity, expansion complexity, 2-adic complexity, and correlation measures. The abstract positions this as a consolidation of advancements in complexity measures for randomness assessment in theoretical computer science and cryptography since Kolmogorov complexity.

Significance. If the coverage is representative and accurate, the survey could serve as a useful reference for researchers working on pseudo-random sequence properties in cryptography. However, the absence of an explicit selection methodology for 'notable' works limits its reliability as a comprehensive resource.

major comments (1)
  1. [Abstract and §1] Abstract and §1: The central claim that the survey covers 'notable research' on the specified complexities and relations is load-bearing, yet no criteria, search protocol, citation thresholds, or inclusion/exclusion rules are provided for selecting papers from the past four decades. This omission prevents assessment of completeness or bias, particularly given the focus on linear/quadratic/maximum-order measures while other established ones receive only passing mention.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive feedback on our survey. We address the major comment below and will incorporate revisions to enhance transparency.

read point-by-point responses

  1. Referee: [Abstract and §1] Abstract and §1: The central claim that the survey covers 'notable research' on the specified complexities and relations is load-bearing, yet no criteria, search protocol, citation thresholds, or inclusion/exclusion rules are provided for selecting papers from the past four decades. This omission prevents assessment of completeness or bias, particularly given the focus on linear/quadratic/maximum-order measures while other established ones receive only passing mention.

    Authors: We agree that an explicit description of selection criteria would strengthen the manuscript. The survey draws on the authors' expertise to highlight works that have been foundational or highly influential in advancing linear complexity, quadratic complexity, and maximum-order complexity, along with their documented relations to Lempel-Ziv, expansion, 2-adic complexities, and correlation measures over the past four decades. To address the concern, we will revise §1 to include a short paragraph stating that inclusion prioritizes seminal contributions establishing key bounds, algorithms, and interrelations within the explicitly scoped topics. We note that the title and abstract already delimit the focus; other measures receive only contextual mention and are not claimed to be exhaustively covered. This addition will clarify the curation approach without converting the survey into a systematic review. revision: yes

Circularity Check

0 steps flagged

No circularity: pure literature survey with no derivations or predictions

full rationale

This paper is a survey that reviews existing literature on complexity measures for pseudo-random sequences. It presents no original derivations, equations, predictions, or fitted parameters. The abstract and structure describe a review of notable research over four decades without claiming any new results that could reduce to inputs by construction. No self-citation chains or ansatzes are load-bearing for any claimed derivation because none exist. The choice of which measures to cover is a scope decision, not a mathematical reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Survey paper introduces no new mathematical claims, parameters, or entities; all content draws from prior literature without additional axioms or free parameters required for a central derivation.

pith-pipeline@v0.9.0 · 5586 in / 1146 out tokens · 30074 ms · 2026-05-24T00:42:55.732927+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

76 extracted references · 76 canonical work pages

  1. [1]

    When good randomness goes bad: virtual machine reset vulnerabilities and hedging deployed cryptography

    T. Ristenpart and S. Yilek, “When good randomness goes bad: virtual machine reset vulnerabilities and hedging deployed cryptography.” in Network and Distributed System Security (NDSS) Symposium, 2010

    work page 2010

  2. [2]

    An analysis of NIST SP 800-90A,

    J. Woodage and D. Shumow, “An analysis of NIST SP 800-90A,” in Advances in Cryptology – EUROCRYPT 2019, Y. Ishai and V. Rijmen, Eds. Cham: Springer International Publishing, 2019, Book Section, pp. 151–180

    work page 2019

  3. [3]

    Dual EC: a standardized back door,

    D. J. Bernstein, T. Lange, and R. Niederhagen, “Dual EC: a standardized back door,” 2015. [Online]. Available: https: //eprint.iacr.org/2015/767

    work page 2015

  4. [4]

    On the pos- sibility of a backdoor in the Micali-Schnorr generator,

    H. Davis, M. D. Green, N. Heninger, K. Ryan, and A. Suhl, “On the pos- sibility of a backdoor in the Micali-Schnorr generator,” inPublic-Key Cryptography – PKC 2024, Q. Tang and V. Teague, Eds. Cham: Springer Nature Switzerland, 2024, pp. 352–386

    work page 2024

  5. [5]

    Recommendation for random number gener- ation using deterministic random bit generators,

    E. Barker and J. Kelsey, “Recommendation for random number gener- ation using deterministic random bit generators,”NIST(National Insti- tute of Standards and Technology), Special Publication, jun 2015. 35

    work page 2015

  6. [6]

    Application of LFSRsfor parallel se- quence generation in cryptologic algorithms,

    S. Mukhopadhyay and P. Sarkar, “Application of LFSRsfor parallel se- quence generation in cryptologic algorithms,” inComputational Science and Its Applications - ICCSA 2006, M. Gavrilova, O. Gervasi, V. Ku- mar, C. J. K. Tan, D. Taniar, A. Lagan´ a, Y. Mun, and H. Choo, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 436–445

    work page 2006

  7. [7]

    A. A. Kuznetsov, O. V. Potii, N. A. Poluyanenko, Y. I. Gorbenko, and N. Kryvinska,Areas of Application for Nonlinear Shift Registers in PRS Generators. Cham: Springer International Publishing, 2022, pp. 295– 318

    work page 2022

  8. [8]

    Grundlagen der wahrscheinlichkeitsrechnung,

    R. V. Mises, “Grundlagen der wahrscheinlichkeitsrechnung,”Mathema- tische Zeitschrift, vol. 5, no. 1, pp. 52–99, mar 1919

    work page 1919

  9. [9]

    On the concept of a random sequence,

    A. Church, “On the concept of a random sequence,”Bulletin of the American Mathematical Society, vol. 46, no. 2, pp. 130–135, feb 1940

    work page 1940

  10. [10]

    S. W. Golomb,Shift Register Sequences: Secure and Limited-access Code Generators, Efficiency Code Generators, Prescribed Property Genera- tors, Mathematical Models (third Revised Edition). World Scientific Publishing Company, 2017

    work page 2017

  11. [11]

    On tables of random numbers,

    A. N. Kolmogorov, “On tables of random numbers,”Theoret. Comput. Sci., vol. 207, no. 2, pp. 387–395, nov 1998

    work page 1998

  12. [12]

    The definition of random sequences,

    P. Martin-L¨ of, “The definition of random sequences,”Information and Control, vol. 9, no. 6, pp. 602–619, dec 1966

    work page 1966

  13. [13]

    Process complexity and effective random tests,

    C. Schnorr, “Process complexity and effective random tests,”Journal of Computer and System Sciences, vol. 7, no. 4, pp. 376–388, aug 1973

    work page 1973

  14. [14]

    D. E. Knuth,The Art of Computer Programming, Volume 2: Seminu- merical Algorithms, 3rd ed. Boston: Addison-Wesley, 1997

    work page 1997

  15. [15]

    E. R. Berlekamp,Algebraic Coding Theory. Singapore: World Scientific Publishing Company, oct 1968

    work page 1968

  16. [16]

    Shift-register synthesis and BCH decoding,

    J. Massey, “Shift-register synthesis and BCH decoding,”IEEE Trans- actions on Information Theory, vol. 15, no. 1, pp. 122–127, jan 1969

    work page 1969

  17. [17]

    Linear complexity and random sequences,

    R. A. Rueppel, “Linear complexity and random sequences,” inAdvances in Cryptology — EUROCRYPT’ 85, F. Pichler, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 1986, pp. 167–188. 36

    work page 1986

  18. [18]

    The probabilistic theory of linear complexity,

    H. Niederreiter, “The probabilistic theory of linear complexity,” inAd- vances in Cryptology — EUROCRYPT ’88, ser. Lecture Notes in Com- puter Science. Springer Berlin Heidelberg, 1988, Book Section, pp. 191–209

    work page 1988

  19. [19]

    Linear complexity and related complexity measures for se- quences,

    ——, “Linear complexity and related complexity measures for se- quences,” inProgress in Cryptology - INDOCRYPT 2003, ser. Lecture Notes in Computer Science. Springer, 2003, Book Section, pp. 1–17

    work page 2003

  20. [20]

    A statistical test suite for random and pseudorandom number generators for cryptographic applications,

    L. E. Bassham, A. L. Rukhin, J. Soto, J. R. Nechvatal, M. E. Smid, S. D. Leigh, M. Levenson, M. Vangel, N. A. Heckert, and D. L. Banks, “A statistical test suite for random and pseudorandom number generators for cryptographic applications,”NIST, sep 2010

    work page 2010

  21. [21]

    Investigations on nonlinear streamcipher systems: construction and evaluation methods,

    C. J. A. Jansen, “Investigations on nonlinear streamcipher systems: construction and evaluation methods,” PhD Thesis, Delft University of Technology, 1989

    work page 1989

  22. [22]

    Feedback shift registers, 2-adic span, and combiners with memory,

    A. Klapper and M. Goresky, “Feedback shift registers, 2-adic span, and combiners with memory,”Journal of Cryptology, vol. 10, no. 2, pp. 111– 147, mar 1997

    work page 1997

  23. [23]

    On the quadratic spans of DeBruijn sequences,

    A. H. Chan and R. A. Games, “On the quadratic spans of DeBruijn sequences,”IEEE Transactions on Information Theory, vol. 36, no. 4, pp. 822–829, 1990

    work page 1990

  24. [24]

    On the use of expansion series for stream ciphers,

    C. Diem, “On the use of expansion series for stream ciphers,”LMS Journal of Computation and Mathematics, vol. 15, pp. 326–340, sep 2012

    work page 2012

  25. [25]

    Linear complexity,k-error linear com- plexity, and the discrete Fourier transform,

    W. Meidl and H. Niederreiter, “Linear complexity,k-error linear com- plexity, and the discrete Fourier transform,”Journal of Complexity, vol. 18, no. 1, pp. 87–103, mar 2002

    work page 2002

  26. [26]

    Pseudorandom sequences,

    A. Topuzo˘ glus and A. Winterhof, “Pseudorandom sequences,” inTop- ics in Geometry, Coding Theory and Cryptography, A. Garcia and H. Stichtenoth, Eds. Springer, 2006, pp. 135–166

    work page 2006

  27. [27]

    Analysis of the Berlekamp-Massey linear feedback shift-register synthesis algorithm,

    F. G. Gustavson, “Analysis of the Berlekamp-Massey linear feedback shift-register synthesis algorithm,”IBM J. Res. Dev., vol. 20, no. 3, pp. 204–212, may 1976

    work page 1976

  28. [28]

    On the equivalence between Berlekamp’s and Euclid’s algorithms ,

    J. Dornstetter, “On the equivalence between Berlekamp’s and Euclid’s algorithms ,”IEEE Transactions on Information Theory, vol. 33, no. 3, pp. 428–431, may 1987. 37

    work page 1987

  29. [29]

    Sequences with almost perfect linear complex- ity profiles and curves over finite fields,

    C. Xing and K. Y. Lam, “Sequences with almost perfect linear complex- ity profiles and curves over finite fields,”IEEE Transactions on Infor- mation Theory, vol. 45, no. 4, pp. 1267–1270, may 1999

    work page 1999

  30. [30]

    An algorithm for shifted continued fraction expansions in parallel linear time,

    H. Niederreiter and M. Vielhaber, “An algorithm for shifted continued fraction expansions in parallel linear time,”Theoretical Computer Sci- ence, vol. 226, no. 1, pp. 93–104, sep 1999

    work page 1999

  31. [31]

    Some computable complexity measures for binary se- quences,

    H. Niederreiter, “Some computable complexity measures for binary se- quences,” inSEquences and Their Applications (SETA). Springer Lon- don, 1999, pp. 67–78

    work page 1999

  32. [32]

    Jungnickel,Finite Fields: Structure and Arithmetics

    D. Jungnickel,Finite Fields: Structure and Arithmetics. B.I. Wis- senschaftsverlag, jan 1993

    work page 1993

  33. [33]

    Linear complexity of periodic se- quences: a general theory,

    J. L. Massey and S. Serconek, “Linear complexity of periodic se- quences: a general theory,” inAdvances in Cryptology — CRYPTO ’96, N. Koblitz, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996, pp. 358–371

    work page 1996

  34. [34]

    A Fourier transform approach to the linear complexity of non- linearly filtered sequences,

    ——, “A Fourier transform approach to the linear complexity of non- linearly filtered sequences,” inAdvances in Cryptology - CRYPTO’94. Berlin, Germany: Springer, jul 1994, pp. 332–340

    work page 1994

  35. [35]

    R. E. Blahut,Theory and Practice of Error Control Codes. Addison- Wesley Publishing Company, 1983

    work page 1983

  36. [36]

    E. S. Selmer,Linear Recurrence Relations Over Finite Fields. Depart- ment of Informatics, University of Bergen, 1966

    work page 1966

  37. [37]

    On the linear complexity of Leg- endre sequences,

    C. Ding, T. Hesseseth, and W. Shan, “On the linear complexity of Leg- endre sequences,”IEEE Transactions on Information Theory, vol. 44, no. 3, pp. 1276–1278, may 1998

    work page 1998

  38. [38]

    Lower bounds on the linear complexity of the discrete logarithm in finite fields,

    W. Meidl and A. Winterhof, “Lower bounds on the linear complexity of the discrete logarithm in finite fields,”IEEE Transactions on Informa- tion Theory, vol. 47, no. 7, pp. 2807–2811, nov 2001

    work page 2001

  39. [39]

    Linear complexity overGF(p) and trace representation of Lempel-Cohn-Eastman sequences,

    T. Helleseth, S.-H. Kim, and J.-S. No, “Linear complexity overGF(p) and trace representation of Lempel-Cohn-Eastman sequences,” inPro- ceedings IEEE International Symposium on Information Theory. IEEE, 2003

    work page 2003

  40. [40]

    Shparlinski,Cryptographic Applications of Analytic Number Theory

    I. Shparlinski,Cryptographic Applications of Analytic Number Theory. Basel, Switzerland: Birkh¨ auser, 2003. 38

    work page 2003

  41. [41]

    R. A. Rueppel,Analysis and Design of Stream Ciphers. Springer Berlin Heidelberg, 1986

    work page 1986

  42. [42]

    On the expected value of the linear complexity and thek-error linear complexity of periodic sequences,

    W. Meidl and H. Niederreiter, “On the expected value of the linear complexity and thek-error linear complexity of periodic sequences,” IEEE Transactions on Information Theory, vol. 48, no. 11, pp. 2817– 2825, 2002

    work page 2002

  43. [43]

    On the quadratic spans of periodic sequences,

    A. H. Chan and R. A. Games, “On the quadratic spans of periodic sequences,” inAdvances in Cryptology — CRYPTO’ 89 Proceedings, ser. Lecture Notes in Computer Science. Springer, 1990, Book Section, pp. 82–89

    work page 1990

  44. [44]

    On the quadratic span of binary sequences,

    A. Youssef and G. Gong, “On the quadratic span of binary sequences,” inProceeding of the 20th Biennial Symposium on Communications, Queen’s university, 2000, pp. 159–163

    work page 2000

  45. [45]

    On the quadratic span of binary sequences,

    P. Rizomiliotis, N. Kolokotronis, and N. Kalouptsidis, “On the quadratic span of binary sequences,”IEEE Transactions on Information Theory, vol. 51, no. 5, pp. 1840–1848, apr 2005

    work page 2005

  46. [46]

    The shortest feedback shift register that can generate a given sequence,

    C. Jansen and D. Boekee, “The shortest feedback shift register that can generate a given sequence,” inAdvances in Cryptology – CRYPTO’89 Proceedings, ser. Lecture Notes in Computer Science. Springer, 1990, Book Section, pp. 90–99

    work page 1990

  47. [47]

    The maximum order complexity of sequence ensembles,

    C. Jansen, “The maximum order complexity of sequence ensembles,” inAdvances in Cryptology — EUROCRYPT ’91, ser. Lecture Notes in Computer Science. Springer, 1991, Book Section, pp. 153–159

    work page 1991

  48. [48]

    Linear size finite automata for the set of all subwords of a word - an outline of results,

    A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, and R. M. Mc- Connell, “Linear size finite automata for the set of all subwords of a word - an outline of results,”Bulletin of the EATCS, vol. 21, pp. 12–20, 1983

    work page 1983

  49. [49]

    Results on the nonlinear span of binary sequences,

    P. Rizomiliotis and N. Kalouptsidis, “Results on the nonlinear span of binary sequences,”IEEE Transactions on Information Theory, vol. 51, no. 4, pp. 1555–1563, apr 2005

    work page 2005

  50. [50]

    On the nonlin- ear complexity and Lempel–Ziv complexity of finite length sequences,

    K. Limniotis, N. Kolokotronis, and N. Kalouptsidis, “On the nonlin- ear complexity and Lempel–Ziv complexity of finite length sequences,” IEEE Transactions on Information Theory, vol. 53, no. 11, pp. 4293– 4302, 2007. 39

    work page 2007

  51. [51]

    An approximate distribution for the maxi- mum order complexity,

    D. Erdmann and S. Murphy, “An approximate distribution for the maxi- mum order complexity,”Designs, Codes and Cryptography, vol. 10, no. 3, pp. 325–339, mar 1997

    work page 1997

  52. [52]

    On the Classification of Periodic Binary Sequences into Nonlinear Complexity Classes,

    G. Petrides and J. Mykkeltveit, “On the Classification of Periodic Binary Sequences into Nonlinear Complexity Classes,” inSequences and Their Applications - SETA 2006. Berlin, Germany: Springer, 2006, pp. 209– 222

    work page 2006

  53. [53]

    Composition of recursions and nonlinear complexity of periodic binary sequences,

    ——, “Composition of recursions and nonlinear complexity of periodic binary sequences,”Designs, Codes and Cryptography, vol. 49, no. 1, pp. 251–264, dec 2008

    work page 2008

  54. [54]

    Construction of sequences with high nonlinear complexity from function fields,

    Y. Luo, C. Xing, and L. You, “Construction of sequences with high nonlinear complexity from function fields,”IEEE Transactions on In- formation Theory, vol. 63, no. 12, pp. 7646–7650, aug 2017

    work page 2017

  55. [55]

    Binary sequences with length n and nonlinear complexity not less thann/2,

    S. Liang, X. Zeng, Z. Xiao, and Z. Sun, “Binary sequences with length n and nonlinear complexity not less thann/2,”IEEE Transactions on Information Theory, vol. 69, no. 12, pp. 8116–8125, sep 2023

    work page 2023

  56. [56]

    Constructing periodic binary sequences with maximum nonlinear span,

    P. Rizomiliotis, “Constructing periodic binary sequences with maximum nonlinear span,”IEEE Transactions on Information Theory, vol. 52, no. 9, pp. 4257–4261, aug 2006

    work page 2006

  57. [57]

    Investigations on periodic sequences with maximum nonlinear complexity,

    Z. Sun, X. Zeng, C. Li, and T. Helleseth, “Investigations on periodic sequences with maximum nonlinear complexity,”IEEE Transactions on Information Theory, vol. 63, no. 10, pp. 6188–6198, jun 2017

    work page 2017

  58. [58]

    Further investi- gations on nonlinear complexity of periodic binary sequences,

    Q. Yuan, C. Li, X. Zeng, T. Helleseth, and D. He, “Further investi- gations on nonlinear complexity of periodic binary sequences,”IEEE Transactions on Information Theory, pp. 1–1, 2024

    work page 2024

  59. [59]

    On the complexity of finite sequences,

    A. Lempel and J. Ziv, “On the complexity of finite sequences,”IEEE Transactions on Information Theory, vol. 22, no. 1, pp. 75–81, jan 1976

    work page 1976

  60. [60]

    Expansion complexity and linear complexity of sequences over finite fields,

    L. Merai, H. Niederreiter, and A. Winterhof, “Expansion complexity and linear complexity of sequences over finite fields,”Cryptography and Communications-Discrete-Structures Boolean Functions and Sequences, vol. 9, no. 4, pp. 501–509, 2017

    work page 2017

  61. [61]

    Maximum-order complexity and correlation measures,

    L. I¸ sık and A. Winterhof, “Maximum-order complexity and correlation measures,”Cryptography, vol. 1, no. 1, p. 7, may 2017. 40

    work page 2017

  62. [62]

    Correlation measure, linear complexity and maximum order complexity for families of binary sequences,

    Z. Chen, A. I. G´ omez, D. G´ omez-P´ erez, and A. Tirkel, “Correlation measure, linear complexity and maximum order complexity for families of binary sequences,”Finite Fields and Their Applications, vol. 78, p. 101977, feb 2022

    work page 2022

  63. [63]

    Periodic sequences with largek-error linear complex- ity,

    H. Niederreiter, “Periodic sequences with largek-error linear complex- ity,”IEEE Transactions on Information Theory, vol. 49, no. 2, pp. 501– 505, feb 2003

    work page 2003

  64. [64]

    On the complexities of De- Bruijn sequences,

    A. H. Chan, R. A. Games, and E. L. Key, “On the complexities of De- Bruijn sequences,”Journal of Combinatorial Theory, Series A, vol. 33, no. 3, pp. 233–246, nov 1982

    work page 1982

  65. [65]

    There are no DeBruijn sequences of spannwith com- plexity 2n−1+n+1,

    R. A. Games, “There are no DeBruijn sequences of spannwith com- plexity 2n−1+n+1,”Journal of Combinatorial Theory, Series A, vol. 34, no. 2, pp. 248–251, mar 1983

    work page 1983

  66. [66]

    Linear spans of modified DeBruijn se- quences,

    G. Mayhew and S. Golomb, “Linear spans of modified DeBruijn se- quences,”IEEE Transactions on Information Theory, vol. 36, no. 5, pp. 1166–1167, 1990

    work page 1990

  67. [67]

    Minimal polynomials of the modified DeBruijn sequences,

    G. M. Kyureghyan, “Minimal polynomials of the modified DeBruijn sequences,”Discrete Applied Mathematics, vol. 156, no. 9, pp. 1549– 1553, may 2008

    work page 2008

  68. [68]

    New results on the minimal polynomials of modified DeBruijn sequences,

    Y.-J. Dong, T. Tian, W.-F. Qi, and Z.-X. Wang, “New results on the minimal polynomials of modified DeBruijn sequences,”Finite Fields and Their Applications, vol. 60, p. 101583, nov 2019

    work page 2019

  69. [69]

    The minimal polynomials of modified DeBruijn sequences revisited,

    H.-Y. Wang, Q.-X. Zheng, Z.-X. Wang, and W.-F. Qi, “The minimal polynomials of modified DeBruijn sequences revisited,”Finite Fields and Their Applications, vol. 68, p. 101735, dec 2020

    work page 2020

  70. [70]

    The lower bound of the quadratic spans of DeBruijn sequences,

    L. H. Khachatrian, “The lower bound of the quadratic spans of DeBruijn sequences,”Designs, Codes and Cryptography, vol. 3, no. 1, pp. 29–32, mar 1993

    work page 1993

  71. [71]

    Cryptanalysis based on 2-adic rational approximation,

    A. Klapper and M. Goresky, “Cryptanalysis based on 2-adic rational approximation,” inAdvances in Cryptology — CRYPTO’ 95. Springer Berlin Heidelberg, 1995, pp. 262–273

    work page 1995

  72. [72]

    Maximum-order complexity and 2-adic complexity,

    Z. Chen, Z. Chen, J. Obrovsky, and A. Winterhof, “Maximum-order complexity and 2-adic complexity,”arXiv, 2023. 41

    work page 2023

  73. [73]

    A universal algorithm for sequential data com- pression,

    J. Ziv and A. Lempel, “A universal algorithm for sequential data com- pression,”IEEE Transactions on Information Theory, vol. 23, no. 3, pp. 337–343, may 1977

    work page 1977

  74. [74]

    Compression of individual sequences via variable-rate coding,

    ——, “Compression of individual sequences via variable-rate coding,” IEEE Transactions on Information Theory, vol. 24, no. 5, pp. 530–536, sep 1978

    work page 1978

  75. [75]

    The expansion complexity of ultimately periodic sequences over finite fields,

    Z. Sun, X. Zeng, C. Li, Y. Zhang, and L. Yi, “The expansion complexity of ultimately periodic sequences over finite fields,”IEEE Transactions on Information Theory, vol. 67, no. 11, pp. 7550–7560, nov 2021

    work page 2021

  76. [76]

    Linear complexity profile of binary sequences with small correlation measure,

    N. Brandst¨ atter and A. Winterhof, “Linear complexity profile of binary sequences with small correlation measure,”Periodica Mathematica Hun- garica, vol. 52, no. 2, pp. 1–8, jun 2006. 42 Algorithm 1:Generation of minimal polynomial fors Input:A binary sequences=s 0s1s2 . . . Output:m=M n(s) the minimal feedback polynomialhgeneratings n // Initialization ...

    work page 2006