Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Applicable Algebra in Engineering, Communication and Computing 2/2022

22-06-2020 | Original Paper

A new lower bound on the family complexity of Legendre sequences

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

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 2/2022

Login to get access
share
SHARE

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.
Literature
2.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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)
39.
go back to reference 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)
Metadata
Title
A new lower bound on the family complexity of Legendre sequences
Authors
Yağmur Çakıroğlu
Oğuz Yayla
Publication date
22-06-2020
Publisher
Springer Berlin Heidelberg
Published in
Applicable Algebra in Engineering, Communication and Computing / Issue 2/2022
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-020-00442-y

Other articles of this Issue 2/2022

Applicable Algebra in Engineering, Communication and Computing 2/2022 Go to the issue

Premium Partner