Skip to main content
Erschienen in:

22.06.2020 | Original Paper

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

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

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!

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!

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!

Literatur
2.
Zurück zum Zitat 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. 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
3.
Zurück zum Zitat 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 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
8.
Zurück zum Zitat Ding, C., Hesseseth, T., Shan, W.: On the linear complexity of Legendre sequences. IEEE Trans. Inf. Theory 44(3), 1276–1278 (1998)MathSciNetCrossRef Ding, C., Hesseseth, T., Shan, W.: On the linear complexity of Legendre sequences. IEEE Trans. Inf. Theory 44(3), 1276–1278 (1998)MathSciNetCrossRef
9.
Zurück zum Zitat Dummit, D.S., Foote, R.M.: Abstr. Algebra, 3rd edn. Wiley, Hoboken, NJ (2004)MATH Dummit, D.S., Foote, R.M.: Abstr. Algebra, 3rd edn. Wiley, Hoboken, NJ (2004)MATH
10.
Zurück zum Zitat 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)) 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))
12.
Zurück zum Zitat Gauss, C.F.: Untersuchungen über höhere Arithmetik. Deutsch herausgegeben von H. Maser. Chelsea Publishing Co., New York (1965) Gauss, C.F.: Untersuchungen über höhere Arithmetik. Deutsch herausgegeben von H. Maser. Chelsea Publishing Co., New York (1965)
13.
Zurück zum Zitat Golomb, S.W., Gong, G.: Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar. Cambridge University Press, Cambridge (2005)CrossRef Golomb, S.W., Gong, G.: Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar. Cambridge University Press, Cambridge (2005)CrossRef
19.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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
26.
Zurück zum Zitat Menezes, A.J., Katz, J., Van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)MATH Menezes, A.J., Katz, J., Van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)MATH
28.
Zurück zum Zitat Niederreiter, H.: Random number generation and quasi-Monte Carlo methods, vol. 63. Siam, Philadelphia (1992)CrossRef Niederreiter, H.: Random number generation and quasi-Monte Carlo methods, vol. 63. Siam, Philadelphia (1992)CrossRef
30.
Zurück zum Zitat Paley, R.E.: On orthogonal matrices. Journal of Mathematics and Physics 12(1–4), 311–320 (1933)CrossRef Paley, R.E.: On orthogonal matrices. Journal of Mathematics and Physics 12(1–4), 311–320 (1933)CrossRef
31.
Zurück zum Zitat Rivat, J., Sárközy, A.: On Pseudorandom Sequences and Their Application. Springer, Berlin (2006)CrossRef Rivat, J., Sárközy, A.: On Pseudorandom Sequences and Their Application. Springer, Berlin (2006)CrossRef
36.
Zurück zum Zitat Topuzoğlu, A., Winterhof, A.: Pseudorandom sequences. In: Topics in geometry, coding theory and cryptography, pp. 135–166. Springer, Berlin (2006) Topuzoğlu, A., Winterhof, A.: Pseudorandom sequences. In: Topics in geometry, coding theory and cryptography, pp. 135–166. Springer, Berlin (2006)
37.
39.
Zurück zum Zitat 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) 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)
Metadaten
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