nach oben

Applicable Algebra in Engineering, Communication and Computing

Tipp

A new lower bound on the family complexity of Legendre sequences

verfasst von: Yağmur Çakıroğlu, Oğuz Yayla

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 2/2022

Einloggen

Abstract

In this paper we study a family of Legendre sequences and its pseudo-randomness in terms of their family complexity. We present an improved lower bound on the family complexity of a family based on the Legendre symbol of polynomials over a finite field. The new bound depends on the Lambert W function and the number of elements in a finite field belonging to its proper subfield. Moreover, we present another lower bound which is a simplified version and approximates the new bound. We show that both bounds are better than previously known ones.

Vorheriger Artikel A recurrent construction of irreducible polynomials of fixed degree over finite fields

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Ahlswede, R., Khachatrian, L.H., Mauduit, C., Sárközy, A.: A complexity measure for families of binary sequences. Period. Math. Hungar. 46(2), 107–118 (2003). https://doi.org/10.1023/A:1025962825241 MathSciNetCrossRefMATH

Ahlswede, R., Mauduit, C., Sárközy, A.: Large families of pseudorandom sequences of \(k\) symbols and their complexity. I. In: General theory of information transfer and combinatorics, Lecture Notes in Comput. Sci., vol. 4123, pp. 293–307. Springer, Berlin (2006). https://doi.org/10.1007/11889342_16

Ahlswede, R., Mauduit, C., Sárközy, A.: Large families of pseudorandom sequences of \(k\) symbols and their complexity. II. In: General theory of information transfer and combinatorics, Lecture Notes in Comput. Sci., vol. 4123, pp. 308–325. Springer, Berlin (2006). https://doi.org/10.1007/11889342_17

Aly, H., Winterhof, A.: On the \(k\)-error linear complexity over \(\mathbb{F}_{p}\) of Legendre and Sidelnikov sequences. Des. Codes Cryptogr. 40(3), 369–374 (2006). https://doi.org/10.1007/s10623-006-0023-5 MathSciNetCrossRefMATH

Balasubramanian, R., Dartyge, C., Mosaki, E.: Sur la complexité de familles d’ensembles pseudo-aléatoires. Annales de l’Institut Fourier 64(1), 267–296 (2014). https://doi.org/10.5802/aif.2847 MathSciNetCrossRefMATH

Chebolu, S.K., Mináč, J.: Counting irreducible polynomials over finite fields using the inclusion-exclusion principle. Math. Mag. 84(5), 369–371 (2011). https://doi.org/10.4169/math.mag.84.5.369 CrossRefMATH

Corless, R.M., Gonnet, G.H., Hare, D.E.G., Jeffrey, D.J., Knuth, D.E.: On the Lambert \(W\) function. Adv. Comput. Math. 5(4), 329–359 (1996). https://doi.org/10.1007/BF02124750 MathSciNetCrossRefMATH

Ding, C., Hesseseth, T., Shan, W.: On the linear complexity of Legendre sequences. IEEE Trans. Inf. Theory 44(3), 1276–1278 (1998) MathSciNetCrossRef

Dummit, D.S., Foote, R.M.: Abstr. Algebra, 3rd edn. Wiley, Hoboken, NJ (2004) MATH

10.

Euler, L.: De serie lambertina plurimisque eius insignibus proprietatibus. Acta Academiae Scientarum Imperialis Petropolitinae 1779, 1783, pp. 29–51 6, 350–369 (1921 (orig. date 1779))

11.

Folláth, J.: Construction of pseudorandom binary sequences using additive characters over GF( \(2^k\)) II. Periodica Mathematica Hungarica 60(2), 127–135 (2010). https://doi.org/10.1007/s10998-010-2127-y MathSciNetCrossRefMATH

12.

Gauss, C.F.: Untersuchungen über höhere Arithmetik. Deutsch herausgegeben von H. Maser. Chelsea Publishing Co., New York (1965)

13.

Golomb, S.W., Gong, G.: Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar. Cambridge University Press, Cambridge (2005) CrossRef

14.

Goubin, L., Mauduit, C., Sárközy, A.: Construction of large families of pseudorandom binary sequences. J. Number Theory 106(1), 56–69 (2004). https://doi.org/10.1016/j.jnt.2003.12.002 MathSciNetCrossRefMATH

15.

Gyarmati, K.: Concatenation of pseudorandom binary sequences. Period. Math. Hungar. 58(1), 99–120 (2009). https://doi.org/10.1007/s10998-009-9099-x MathSciNetCrossRefMATH

16.

Gyarmati, K.: On the complexity of a family of Legendre sequences with irreducible polynomials. Finite Fields Appl. 33, 175–186 (2015). https://doi.org/10.1016/j.ffa.2014.11.004 MathSciNetCrossRefMATH

17.

Gyarmati, K., Mauduit, C., Sárközy, A.: Measures of pseudorandomness of families of binary lattices, II (a further construction). Publ. Math. Debrecen 80(3–4), 479–502 (2012). https://doi.org/10.5486/PMD.2012.5197 MathSciNetCrossRefMATH

18.

Gyarmati, K., Mauduit, C., Sárközy, A.: The cross-correlation measure for families of binary sequences, p. 126–143. Cambridge University Press (2014). https://doi.org/10.1017/CBO9781139696456.009

19.

Hofer, R., Mérai, L., Winterhof, A.: Measures of pseudorandomness: arithmetic autocorrelation and correlation measure. Number theory–Diophantine problems. Uniform distribution and applications, pp. 303–312. Springer, Cham (2017)

20.

Hoffstein, J., Lieman, D.: The distribution of the quadratic symbol in function fields and a faster mathematical stream cipher. In: Cryptography and Computational Number Theory, pp. 59–68. Birkhäuser Basel, Basel (2001)

21.

Hoorfar, A., Hassani, M.: Inequalities on the lambert w function and hyperpower function. J. Inequal. Pure and Appl. Math 9(2), 5–9 (2008) MathSciNetMATH

22.

Lidl, R., Niederreiter, H.: Finite Fields, Encyclopedia of Mathematics and its Applications, vol. 20, 2nd edn. Cambridge University Press, Cambridge (1997). With a foreword by P. M. Cohn

23.

Mauduit, C., Sárközy, A.: On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol. Acta Arith. 82(4), 365–377 (1997). https://doi.org/10.4064/aa-82-4-365-377

24.

Mauduit, C., Sárközy, A.: Family complexity and VC-dimension. In: Information Theory, Combinatorics, and Search Theory, Lecture Notes in Comput. Sci., vol. 7777, pp. 346–363. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36899-8_15

25.

Meidl, W., Winterhof, A.: On the autocorrelation of cyclotomic generators. In: Finite fields and applications, Lecture Notes in Comput. Sci., vol. 2948, pp. 1–11. Springer, Berlin (2004). https://doi.org/10.1007/978-3-540-24633-6_1

26.

Menezes, A.J., Katz, J., Van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996) MATH

27.

Mullen, G.L., Panario, D. (eds.): Handbook of finite fields. Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL (2013). https://doi.org/10.1201/b15006

28.

Niederreiter, H.: Random number generation and quasi-Monte Carlo methods, vol. 63. Siam, Philadelphia (1992) CrossRef

29.

Niederreiter, H., Winterhof, A.: Applied Number Theory. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22321-6 CrossRefMATH

30.

Paley, R.E.: On orthogonal matrices. Journal of Mathematics and Physics 12(1–4), 311–320 (1933) CrossRef

31.

Rivat, J., Sárközy, A.: On Pseudorandom Sequences and Their Application. Springer, Berlin (2006) CrossRef

32.

Sárközy, A.: A finite pseudorandom binary sequence. Studia Sci. Math. Hungar. 38, 377–384 (2001). https://doi.org/10.1556/SScMath.38.2001.1-4.28 MathSciNetCrossRefMATH

33.

Shparlinski, I.: Cryptographic applications of analytic number theory, Progress in Computer Science and Applied Logic, vol. 22. Birkhäuser Verlag, Basel (2003). https://doi.org/10.1007/978-3-0348-8037-4. Complexity lower bounds and pseudorandomness

34.

Sárközy, A.: On pseudorandomness of families of binary sequences. Discrete Appl. Math. 216, 670–676 (2017). https://doi.org/10.1016/j.dam.2015.07.031 MathSciNetCrossRefMATH

35.

The Sage Developers: SageMath, the Sage Mathematics Software System (Version 9.0) (2020). https://www.sagemath.org

36.

Topuzoğlu, A., Winterhof, A.: Pseudorandom sequences. In: Topics in geometry, coding theory and cryptography, pp. 135–166. Springer, Berlin (2006)

37.

Turyn, R.J.: The linear generation of the Legendre sequence. SIAM J. Appl. Math. 12(1), 115 (1964) MathSciNetCrossRef

38.

Valluri, S.R., Jeffrey, D.J., Corless, R.M.: Some applications of the lambert W function to physics. Canad. J. Phys. 78(9), 823–831 (2000). https://doi.org/10.1139/p00-065 CrossRef

39.

Weil, A.: Sur les courbes algébriques et les variétés qui s’en déduisent. Actualités Sci. Ind., no. 1041 = Publ. Inst. Math. Univ. Strasbourg 7 (1945). Hermann et Cie., Paris (1948)

40.

Winterhof, A., Yayla, O.: Family complexity and cross-correlation measure for families of binary sequences. Ramanujan J. 39(3), 639–645 (2016). https://doi.org/10.1007/s11139-014-9649-5 MathSciNetCrossRefMATH

Titel: A new lower bound on the family complexity of Legendre sequences
verfasst von: Yağmur Çakıroğlu
Oğuz Yayla
Publikationsdatum: 22.06.2020
Verlag: Springer Berlin Heidelberg
Erschienen in: Applicable Algebra in Engineering, Communication and Computing / Ausgabe 2/2022
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-020-00442-y

Springer Professional

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2022

A recurrent construction of irreducible polynomials of fixed degree over finite fields

Some classes of permutation polynomials of the form over

Colouring simplicial complexes via the Lechuga–Murillo’s model

Multiple-rate error-correcting coding scheme

Correction to: Some classes of permutation polynomials of the form over

Double quadratic residue codes and self-dual double cyclic codes