Families of sequences with good family complexity and cross-correlation measure

Kenan Doğan; Murat Şahin; Oğuz Yayla; Kenan Doğan; Murat Şahin; Oğuz Yayla

doi:10.3934/math.2025003

AIMS Mathematics

2025, Volume 10, Issue 1: 38-55. doi: 10.3934/math.2025003

Previous Article Next Article

Research article

Families of sequences with good family complexity and cross-correlation measure

1.
Graduate School of Natural and Applied Sciences, Department of Mathematics, Ankara University, Altındağ 06110, Ankara, Türkiye
2.
Department of Mathematics, Ankara University, Tandoğan 06100, Ankara, Türkiye
3.
Institute of Applied of Mathematics, Middle East Technical University, Çankaya 06800, Ankara, Türkiye
^†This publication is a part of the doctoral thesis of Kenan Doğan.

Received: 23 October 2024 Revised: 05 December 2024 Accepted: 11 December 2024 Published: 02 January 2025
MSC : 11K45, 94A55, 94A60

In this paper, we examine the pseudorandomness of a family of sequences with respect to two key measures: family complexity ($ f $-complexity) and cross-correlation measure of order $ \ell $. Our study encompasses sequences over both binary and $ k $-symbol ($ k $-ary) alphabets. We first extend known methods for constructing families of binary pseudorandom sequences and establish a bound on the $ f $-complexity of a large family of binary sequences generated from the Legendre symbols of certain irreducible polynomials. We demonstrate that this family, as well as its dual, exhibits both high family complexity and low cross-correlation measure up to a relatively high order. Additionally, we present a second family of binary sequences with similarly high $ f $-complexity and low cross-correlation measure. Finally, we generalize our results to families of sequences over the $ k $-symbol alphabets.
- binary sequences,
- cross-correlation measure,
- family complexity,
- $ k $-symbols sequences,
- pseudorandomness
Citation: Kenan Doğan, Murat Şahin, Oğuz Yayla. Families of sequences with good family complexity and cross-correlation measure[J]. AIMS Mathematics, 2025, 10(1): 38-55. doi: 10.3934/math.2025003

Related Papers:

Abstract

In this paper, we examine the pseudorandomness of a family of sequences with respect to two key measures: family complexity ($ f $-complexity) and cross-correlation measure of order $ \ell $. Our study encompasses sequences over both binary and $ k $-symbol ($ k $-ary) alphabets. We first extend known methods for constructing families of binary pseudorandom sequences and establish a bound on the $ f $-complexity of a large family of binary sequences generated from the Legendre symbols of certain irreducible polynomials. We demonstrate that this family, as well as its dual, exhibits both high family complexity and low cross-correlation measure up to a relatively high order. Additionally, we present a second family of binary sequences with similarly high $ f $-complexity and low cross-correlation measure. Finally, we generalize our results to families of sequences over the $ k $-symbol alphabets.

References

[1]	R. Ahlswede, L. H. Khachatrian, C. Mauduit, A. Sárközy, A complexity measure for families of binary sequences, Period. Math. Hung., 46 (2003), 107–118. https://doi.org/10.1023/A:1025962825241 doi: 10.1023/A:1025962825241
[2]	R. Ahlswede, C. Mauduit, A. Sárközy, Large families of pseudorandom sequences of k-symbols and their complexity, Ⅰ-Ⅱ, In: General theory of information transfer and combinatorics, Berlin: Springer, 2006.
[3]	N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, V. Rödl, Measures of pseudorandomness for finite sequences: Typical values, Proc. Lond. Math. Soc., 95 (2007), 778–812. https://doi.org/10.1112/plms/pdm027 doi: 10.1112/plms/pdm027
[4]	Y. Çakıroglu, O. Yayla, E. Sercan Yılmaz, The number of irreducible polynomials over finite fields with vanishing trace and reciprocal trace, Des. Codes Cryptogr., 90 (2022), 2407–2417. https://doi.org/10.1007/s10623-022-01088-2 doi: 10.1007/s10623-022-01088-2
[5]	J. Cassaigne, C. Mauduit, A. Sarkozy, On finite pseudorandom binary sequences Ⅶ: The measures of pseudorandomness, Acta Aritmetica-Warszawa, 103 (2002), 97–118.
[6]	Z. Chen, Elliptic curve analogue of Legendre sequences, Monatsh. Math., 154 (2008), 1–10. https://doi.org/10.1007/s00605-008-0520-x doi: 10.1007/s00605-008-0520-x
[7]	Z. Chen, A. Ostafe, A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients, In: International Workshop on the Arithmetic of Finite Fields, Berlin: Springer, 6087 (2010), 73–85. https://doi.org/10.1007/978-3-642-13797-6_6
[8]	J. Dick, F. Pillichshammer, Digital nets and sequences: discrepancy theory and quasi–Monte Carlo integration, Cambridge: Cambridge University Press, 2010.
[9]	X. Du, Z. Lin, On pseudorandom sequences of k-symbols constructed using finite fields, Appl. Algebra Eng. Commun. Comput., 25 (2014), 265–285. https://doi.org/10.1007/s00200-014-0224-5 doi: 10.1007/s00200-014-0224-5
[10]	J. Folláth, Construction of pseudorandom binary sequences using additive characters over GF(2k), Period. Math. Hung., 57 (2008), 73–81. https://doi.org/10.1007/s10998-008-7073-1 doi: 10.1007/s10998-008-7073-1
[11]	B. Gergely, On finite pseudorandom sequences of k-symbols, Period. Math. Hung., 47 (2003), 29–44. https://doi.org/10.1023/b:mahu.0000010809.50836.79 doi: 10.1023/b:mahu.0000010809.50836.79
[12]	S. W. Golomb, G. Gong, Signal design for good correlation, Cambridge: Cambridge University Press, 2005.
[13]	D. Gomez, A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences, Period. Math. Hung., 64 (2012), 161–168. https://doi.org/10.1007/s10998-012-3747-1 doi: 10.1007/s10998-012-3747-1
[14]	L. Goubin, C. Mauduit, A. Sárközy, Construction of large families of pseudorandom binary sequences, J. Number Theory, 106 (2004), 56–69. https://doi.org/10.1016/j.jnt.2003.12.002 doi: 10.1016/j.jnt.2003.12.002
[15]	K. Gyarmati, On a family of pseudorandom binary sequences, Period. Math. Hung., 49 (2004), 45–63. https://doi.org/10.1007/s10998-004-0522-y doi: 10.1007/s10998-004-0522-y
[16]	K. Gyarmati, On the complexity of a family related to the Legendre symbol, Period. Math. Hung., 58 (2009), 209–215. https://doi.org/10.1007/s10998-009-10209-4 doi: 10.1007/s10998-009-10209-4
[17]	K. Gyarmati, Measures of pseudorandomness. In: Finite fields and their applications: character sums and polynomials, Berlin: Springer, 11 (2013), 43–64. https://doi.org/10.1515/9783110283600
[18]	K. Gyarmati, C. Mauduit, A. Sárközy, The cross-correlation measure for families of binary sequences, In: Applied algebra and number theory, Cambridge: Cambridge University Press, 126–143, 2014.
[19]	H. Iwaniec, E. Kowalski, Analytic number theory, Providence, RI: American Mathematical Society, 2004.
[20]	P. L'Ecuyer, R. Simard, Testu01: AC library for empirical testing of random number generators, ACM Transact. Math. Software (TOMS), 33 (2007), 1–40. https://doi.org/10.1145/1268776.1268777 doi: 10.1145/1268776.1268777
[21]	H. Liu, New pseudorandom sequences constructed by quadratic residues and Lehmer numbers, Proc. Amer. Math. Soc., 135 (2007), 1309–1318. https://doi.org/10.1090/S0002-9939-06-08630-8 doi: 10.1090/S0002-9939-06-08630-8
[22]	H. Liu, B. Gao, A large family of pseudorandom sequences of k symbols with length $pq$, Acta Arith., 181 (2017), 1–26. https://doi.org/10.4064/aa8452-5-2017 doi: 10.4064/aa8452-5-2017
[23]	H. Liu, X. Liu, Binary sequence family with both small cross-correlation and large family complexity, Finite Fields Appl., 97 (2024), 102440. https://doi.org/10.1016/j.ffa.2024.102440 doi: 10.1016/j.ffa.2024.102440
[24]	K. Mak, More constructions of pseudorandom sequences of $k$ symbols, Finite Fields Appl., 25 (2014), 222–233. https://doi.org/10.1016/j.ffa.2013.09.006 doi: 10.1016/j.ffa.2013.09.006
[25]	G. Marsaglia, Diehard: a battery of tests of randomness, 1996.
[26]	C. Mauduit, J. Rivat, A. Sárközy, Construction of pseudorandom binary sequences using additive characters, Monatsh. Math., 141 (2004), 197–208. https://doi.org/10.1007/s00605-003-0112-8 doi: 10.1007/s00605-003-0112-8
[27]	C. Mauduit, A. Sárközy, On finite pseudorandom binary sequences. Ⅰ. Measure of pseudorandomness, the Legendre symbol, Acta Arith., 82 (1997), 365–377.
[28]	C. Mauduit, A. Sárközy, On finite pseudorandom sequences of $k$ symbols, Indag. Math., 13 (2002), 89–101.
[29]	C. Mauduit, A. Sárközy, Construction of pseudorandom binary sequences by using the multiplicative inverse, Acta Math. Hung., 108 (2005), 239–252. https://doi.org/10.1007/s10474-005-0222-y doi: 10.1007/s10474-005-0222-y
[30]	L. Mérai, Construction of pseudorandom binary sequences over elliptic curves using multiplicative characters, Publ. Math. Debrecen, 80 (2012), 199–213.
[31]	L. Mérai, The cross-correlation measure of families of finite binary sequences: limiting distributions and minimal values, Discrete Appl. Math., 214 (2016), 153–168. https://doi.org/10.1016/j.dam.2016.06.024 doi: 10.1016/j.dam.2016.06.024
[32]	L. Mérai, On the typical values of the cross-correlation measure, Monatsh. Math., 180 (2016), 83–99. https://doi.org/10.1007/s00605-016-0886-0 doi: 10.1007/s00605-016-0886-0
[33]	L. Mérai, O. Yayla, Improving results on the pseudorandomness of sequences generated via the additive order of a finite field, Discrete Math., 338 (2015), 2020–2025. https://doi.org/10.1016/j.disc.2015.04.015 doi: 10.1016/j.disc.2015.04.015
[34]	H. Niederreiter, A. Winterhof, Applied number theory, Berlin: Springer, 2015.
[35]	A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, A statistical test suite for random and pseudorandom number generators for cryptographic applications, technical report, DTIC Document, 2001.
[36]	A. Sárközy, A. Winterhof, Measures of pseudorandomness for binary sequences constructed using finite fields, Discrete Math., 309 (2009), 1327–1333. https://doi.org/10.1016/j.disc.2008.01.056 doi: 10.1016/j.disc.2008.01.056
[37]	A. Sárközy, On pseudorandomness of families of binary sequences, Discrete Appl. Math., 216 (2017), 670–676. https://doi.org/10.1016/j.dam.2015.07.031 doi: 10.1016/j.dam.2015.07.031
[38]	A. Tietäväinen, Vinogradov's method and some applications, Number Theory Appl., 204 (1999), 261–282.
[39]	A. Topuzoglu, A. Winterhof, Pseudorandom sequences, In: Topics in Geometry, Coding Theory and Cryptography, Dordrecht: Springer, 6 (2007), 135–166. https://doi.org/10.1007/1-4020-5334-4_4
[40]	V. Tóth, Extension of the notion of collision and avalanche effect to sequences of $k$ symbols, Period. Math. Hung., 65 (2012), 229–238. https://doi.org/10.1007/s10998-012-1005-1 doi: 10.1007/s10998-012-1005-1
[41]	A. Weil, On some exponential sums, Proc. Nat. Acad. Sci., 34 (1948), 204–207. https://doi.org/10.1073/pnas.34.5.204 doi: 10.1073/pnas.34.5.204
[42]	A. Winterhof, Some estimates for character sums and applications, Des. Codes Cryptogr., 22 (2001), 123–131. https://doi.org/10.1023/A:1008300619004 doi: 10.1023/A:1008300619004
[43]	A. Winterhof, O. Yayla, Family complexity and cross-correlation measure for families of binary sequences, Ramanujan J., 39 (2016), 639–645. https://doi.org/10.1007/s11139-014-9649-5 doi: 10.1007/s11139-014-9649-5
[44]	J. L. Yucas, Irreducible polynomials over finite fields with prescribed trace/prescribed constant term, Finite Fields Appl., 12 (2006), 211–221. https://doi.org/10.1016/j.ffa.2005.04.006 doi: 10.1016/j.ffa.2005.04.006

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)