Skip to main content
SpringerLink
Log in

On the linear complexity of binary lattices

  • Published:
The Ramanujan Journal Aims and scope Submit manuscript

Abstract

Linear complexity is an important and frequently used measure of unpredictability and pseudorandomness of binary sequences. In this paper our goal is to extend this notion to two dimensions. We will define and study the linear complexity of binary lattices. The linear complexity of a truly random binary lattice will be estimated. Finally, we will analyze the connection between linear complexity and correlation measures, and we will utilize the inequalities obtained in this way for estimating the linear complexity of an important special binary lattice. Finally, we will study the connection between the linear complexity of binary lattices and of the associated binary sequences.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alon, N., Kohayakawa, Y., Mauduit, C., Moreira, C.G., Rödl, V.: Measures of pseudorandomness for finite sequences: typical values. Proc. Lond. Math. Soc. 95, 778–812 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  2. Andics, Á.: On the linear complexity of binary sequences. Ann. Univ. Sci. Bp. 48, 173–180 (2005)

    MathSciNet  MATH  Google Scholar 

  3. Brandstätter, N., Winterhof, A.: Linear complexity profile of binary sequences with small correlation measure. Period. Math. Hung. 52, 1–8 (2006)

    Article  MATH  Google Scholar 

  4. Cassaigne, J., Mauduit, C., Sárközy, A.: On finite pseudorandom binary sequences VII: the measures of pseudorandomness. Acta Arith. 103, 97–118 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  5. Chen, Z., Winterhof, A.: Linear complexity profile of m-ary pseudorandom sequences with small correlation measure. Indag. Math. 20, 631–640 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  6. Feng, X., Dai, Z.: Expected value of the linear complexity of two-dimensional binary sequences. In: Helleseth, T., et al. (eds.) SETA 2004. LNCS, vol. 3486, pp. 113–128. Springer, Berlin (2005)

    Google Scholar 

  7. Gyarmati, K., Mauduit, C., Sárközy, A.: Measures of pseudorandomness of families of binary lattices, I (definitions, a construction using quadratic characters). Publ. Math. (Debr.) 79, 445–460 (2011)

    Article  MATH  Google Scholar 

  8. Gyarmati, K., Mauduit, C., Sárközy, A.: Measures of pseudorandomness of families of binary lattices, II (A further construction.). Publ. Math. (Debr.) 80, 481–504 (2012)

    Google Scholar 

  9. Gyarmati, K., Mauduit, C., Sárközy, A.: Measures of pseudorandomness of finite binary lattices, III. (Q k , correlation, normality, minimal values.). Unif. Distrib. Theory 5, 183–207 (2010)

    MathSciNet  MATH  Google Scholar 

  10. Gyarmati, K., Mauduit, C., Sárközy, A.: Pseudorandom binary sequences and lattices. Acta Arith. 135, 181–197 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  11. Gyarmati, K., Sárközy, A., Stewart, C.L.: On legendre symbol lattices. Unif. Distrib. Theory 4, 81–95 (2009)

    MATH  Google Scholar 

  12. Hubert, P., Mauduit, C., Sárközy, A.: On pseudorandom binary lattices. Acta Arith. 125, 51–62 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  13. Kohayakawa, Y., Mauduit, C., Moreira, C.G., Rödl, V.: Measures of pseudorandomness for finite sequences: minimum and typical values. In: Proceedings of WORDS’03. TUCS Gen. Publ., vol. 27, pp. 159–169. Turku Cent. Comput. Sci, Turku (2003)

    Google Scholar 

  14. Massey, J.L.: Shift-register synthesis and BCH decoding. IEEE Trans. Inf. Theory 15, 122–127 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  15. Mauduit, C., Sárközy, A.: On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the legendre symbol. Acta Arith. 82, 365–377 (1997)

    MathSciNet  MATH  Google Scholar 

  16. Menezes, A., van Oorschot, P.C., Vanstone, S.: Handbook of Applied Cryptography. CRS Press, Boca Raton (1997)

    MATH  Google Scholar 

  17. Rueppel, R.A.: Linear complexity and random sequences. In: Proc. Advances in Cryptology—EUROCRYPT’85, Linz, Austria, April 9–12, 1985. LNCS, vol. 219, pp. 167–188 (1985)

    Google Scholar 

  18. Winterhof, A.: Linear complexity and related complexity measures. In: Woungang, I., et al. (eds.) Selected Topics in Information and Coding Theory. World Scientific, Singapore (2010)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Algebra and Number Theory, Eötvös Loránd University, Pázmány Péter sétány 1/C, 1117, Budapest, Hungary

    Katalin Gyarmati & András Sárközy

  2. Institut de Mathématiques de Luminy, CNRS, FRE 3529, Université Aix-Marseille, 163 avenue de Luminy, 13288, Marseille Cedex 9, France

    Christian Mauduit

  3. Instituto de Matemática Pura e Aplicada, IMPA-CNRS, UMI 2924, Estrada Dona Castorina 110, 22460-320, Rio de Janeiro, RJ, Brazil

    Christian Mauduit

Authors
  1. Katalin Gyarmati
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Christian Mauduit
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. András Sárközy
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Katalin Gyarmati.

Additional information

Research partially supported by Hungarian National Foundation for Scientific Research, Grants No. K72731 and K100291, French-Hungarian exchange program FR-33/2009, the Agence Nationale de la Recherche grant ANR-10-BLAN 0103 MUNUM and the János Bolyai Research Fellowship.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gyarmati, K., Mauduit, C. & Sárközy, A. On the linear complexity of binary lattices. Ramanujan J 32, 185–201 (2013). https://doi.org/10.1007/s11139-012-9433-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11139-012-9433-3

Keywords

Mathematics Subject Classification (2010)

Search

Navigation