On the pseudorandom properties of $ k $-ary Sidel'nikov sequences

Huaning Liu; Yixin Ren

doi:10.3934/amc.2021038

Article Contents

2023, Volume 17, Issue 5: 1072-1085. Doi: 10.3934/amc.2021038

This issue Previous Article Z-complementary pairs with flexible lengths and large zero odd-periodic correlation zones Next Article New self-dual codes from $ 2 \times 2 $ block circulant matrices, group rings and neighbours of neighbours

On the pseudorandom properties of $ k $-ary Sidel'nikov sequences

Huaning Liu and
Yixin Ren^,

Research Center for Number Theory and Its Applications, School of Mathematics, Northwest University, Xi'an 710127, China

^* Corresponding author: Yixin Ren
^* Corresponding author: Yixin Ren

Received: March 2021

Early access: August 2021

Published: October 2023

Abstract Full Text(HTML) Related Papers Cited by

Abstract

In 2002 Mauduit and Sárközy started to study finite sequences of $ k $ symbols

$ E_{N} = \left(e_{1},e_{2},\cdots,e_{N}\right)\in \mathcal{A}^{N}, $

where $ \mathcal{A} = \left\{a_{1},a_{2},\cdots,a_{k}\right\}(k\in \mathbb{N},k\geq 2) $ is a finite set of $ k $ symbols. Later many pseudorandom sequences of $ k $ symbols have been given and studied by using number theoretic methods. In this paper we study the pseudorandom properties of the $ k $-ary Sidel'nikov sequences with length $ q-1 $ by using the estimates for certain character sums with exponential function, where $ q $ is a prime power. Our results show that Sidel'nikov sequences enjoy good well-distribution measure and correlation measure. Furthermore, we prove that the set of size $ \phi(q-1) $ of $ k $-ary Sidel'nikov sequences is collision free and possesses the strict avalanche effect property provided that $ k = o(q^{\frac{1}{4}}) $, where $ \phi $ denotes Euler's totient function.

Keywords:

Mathematics Subject Classification: Primary: 11K45; Secondary: 11B50, 94A55, 94A60.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	R. Ahlswede, C. Mauduit and A. Sárközy, Large families of pseudorandom sequences of $k$ symbols and their complexity-Part Ⅰ, in General Theory of Information Transfer and Combinatorics, Lecture Notes in Comput. Sci., Vol. 4123, Springer, Berlin, 2006,293–307. doi: 10.1007/11889342_16.
[2]	R. Ahlswede, C. Mauduit and A. Sárközy, Large families of pseudorandom sequences of $k$ symbols and their complexity-Part Ⅱ, in General Theory of Information Transfer and Combinatorics, Lecture Notes in Comput. Sci., Vol. 4123, Springer, Berlin, 2006,308–325. doi: 10.1007/11889342_17.
[3]	S. Alaca and G. Millar, Character values of the Sidelnikov-Lempel-Cohn-Eastman sequences, Cryptogr. Commun., 9 (2017), 665-682. doi: 10.1007/s12095-016-0208-3.
[4]	H. Aly and W. Meidl, On the linear complexity and $k$-error linear complexity over $\mathbb{F}_p$ of the $d$-ary Sidelnikov sequence, IEEE Trans. Inform. Theory, 53 (2007), 4755-4761. doi: 10.1109/TIT.2007.909129.
[5]	H. Aly and A. Winterhof, On the $k$-error linear complexity over $\mathbb{F}_p$ of Legendre and Sidelnikov sequences, Des. Codes Cryptogr., 40 (2006), 369-374. doi: 10.1007/s10623-006-0023-5.
[6]	H. Alzer and S. Koumandos, On a trigonometric sum of Vinogradov, J. Number Theory, 105 (2004), 251-261. doi: 10.1016/j.jnt.2003.10.003.
[7]	N. Brandstätter and W. Meidl, On the linear complexity of Sidelnikov sequences over $ \mathbb{F}_{d}$, in: Proceedings of SETA'06, Lecture Notes in Comput. Sci., Vol. 4086, Springer-Verlag, Berlin, Heidelberg, (2006), 47–60.
[8]	N. Brandstätter and W. Meidl, On the linear complexity of Sidelnikov sequences over nonprime fields, J. Complexity, 24 (2008), 648-659. doi: 10.1016/j.jco.2008.04.002.
[9]	Z.-X. Chen, X.-N. Du and C.-H. Wu, Pseudorandomness of certain sequences of $k$ symbols with length $pq$, J. Comput. Sci. Tech., 26 (2011), 276-282. doi: 10.1007/s11390-011-9434-5.
[10]	J.-S. Chung, Y.-S. Kim, T.-H. Lim, J.-S. No and H. Chung, On some properties of $M$-ary Sidelnikov sequences, IEICE Trans. Fundamentals, E92-A (2009), 342-345. doi: 10.1587/transfun.E92.A.342.
[11]	J.-H. Chung and K. Yang, Bounds on the linear complexity and the $1$-error linear complexity over $\mathbb{F}_p$ of $M$-ary Sidelnikov sequences, in: Proceedings of SETA'06, Lecture Notes in Comput. Sci., Vol. 4086, Springer-Verlag, Berlin, Heidelberg, 2006, 74–87. doi: 10.1007/11863854_7.
[12]	T. Cochrane, On a trigonometric inequality of Vinogradov, J. Number Theory, 27 (1987), 9-16. doi: 10.1016/0022-314X(87)90045-X.
[13]	C. Ding and J. Yin, Sets of optimal frequency-hopping sequences, IEEE Trans. Inform. Theory, 54 (2008), 3741-3745. doi: 10.1109/TIT.2008.926410.
[14]	E. Dobrowolski and K. S. Williams, An upper bound for the sum $\sum_{n = a+1}^{a+H}f(n)$ for a certain class of functions $f$, Proc. Amer. Math. Soc., 114 (1992), 29-35. doi: 10.1090/s0002-9939-1992-1068118-6.
[15]	Y.-C. Eun, H.-Y. Song and G. M. Kyureghyan, One-error linear complexity over $\mathbb{F}_p$ of Sidelnikov sequences, in Proc. Int. Conf. Sequ. Appl., Seoul 2004, Lecture Notes in Comput. Sci., Vol. 3486, Springer-Verlag, Berlin, Heidelberg, 2005,154–165. doi: 10.1007/11423461_9.
[16]	M. Z. Garaev, F. Luca, I. E. Shparlinski and A. Winterhof, On the lower bound of the linear complexity over $\mathbb{F}_p$ of Sidelnikov sequences, IEEE Trans. Inform. Theory, 52 (2006), 3299-3304. doi: 10.1109/TIT.2006.876352.
[17]	D. Gomez and A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences, Period. Math. Hungar., 64 (2012), 161-168. doi: 10.1007/s10998-012-3747-1.
[18]	Y. K. Han and K. Yang, On the Sidelnikov sequences as frequency-hopping sequences, IEEE Trans. Inform. Theory, 55 (2009), 4279-4285. doi: 10.1109/TIT.2009.2025569.
[19]	T. Helleseth, S.-H. Kim and J.-S. No, Linear complexity over $\mathbb{F}_p$ and trace representation of Lempel-Cohn-Eastman sequences, IEEE Trans. Inform. Theory, 49 (2003), 1548-1552. doi: 10.1109/TIT.2003.811924.
[20]	T. Helleseth, M. Maas, J. E. Mathiassen and T. Segers, Linear complexity over $\mathbb{F}_p$ of Sidelnikov sequences, IEEE Trans. Inform. Theory, 50 (2004), 2468-2472. doi: 10.1109/TIT.2004.834854.
[21]	Y. Kim, D. Kim and H. Song, Some properties of $2$-dimensional array structure of Sidelnikov sequences of period $q^{d}-1$, Proceedings of IWSDA'13, (2013), 20–23.
[22]	Y.-J. Kim and H.-Y. Song, Cross correlation of Sidel'nikov sequences and their constant multiples, IEEE Trans. Inform. Theory, 53 (2007), 1220-1224. doi: 10.1109/TIT.2006.890723.
[23]	Y.-S. Kim, J.-S. Chung, J.-S. No and H. Chung, On the autocorrelation distributions of Sidelnikov sequences, IEEE Trans. Inform. Theory, 51 (2005), 3303-3307. doi: 10.1109/TIT.2005.853310.
[24]	Y.-S. Kim, J.-S. Chung, J.-S. No and H. Chung, On the linear complexity over $\mathbb{F}_p$ of $M$-ary Sidelnikov sequences, in Proc. IEEE ISIT 2005, Sept. (2005), 2007–2011. doi: 10.1109/ISIT.2005.1523697.
[25]	Y.-S. Kim, J.-S. Chung, J.-S. No and H. Chung, Linear complexity over $\mathbb{F}_p$ of ternary Sidelnikov sequences, in: Proceedings of SETA'06, Lecture Notes in Comput. Sci., Vol. 4086, Springer-Verlag, Berlin, Heidelberg, (2006), 61–73. doi: 10.1007/11863854_6.
[26]	Y.-S. Kim, J.-S. Chung, J.-S. No and H. Chung, New families of $M$-ary sequences with low correlation constructed from Sidelnikov sequences, IEEE Trans. Inform. Theory, 54 (2008), 3768-3774. doi: 10.1109/TIT.2008.926428.
[27]	Y.-T. Kim, D. S. Kim and H.-Y. Song, New $M$-ary sequence families with low correlation from the array structure of Sidelnikov sequences, IEEE Trans. Inform. Theory, 61 (2015), 655-670. doi: 10.1109/TIT.2014.2371461.
[28]	G. M. Kyureghyan and A. Pott, On the linear complexity of the Sidelnikov-Lempel-Cohn-Eastman sequences, Des. Codes Cryptogr., 29 (2003), 149-164. doi: 10.1023/A:1024156525801.
[29]	A. Lempel, M. Cohn and W. L. Eastman, A class of balanced binary sequences with optimal autocorrelation properties, IEEE Trans. Inform. Theory, 23 (1977), 38-42. doi: 10.1109/TIT.1977.1055672.
[30]	A. Lempel and H. Greenberger, Families of sequences with optimal Hamming correlation properties, IEEE Trans. Inform. Theory, 20 (1974), 90-94. doi: 10.1109/TIT.1974.1055169.
[31]	H. Liu and B. Gao, A large family of pseudorandom sequences of $k$ symbols with length $pq$, Acta Arith., 181 (2017), 1-26. doi: 10.4064/aa8452-5-2017.
[32]	K.-H. Mak, More constructions of pseudorandom sequences of $k$ symbols, Finite Fields Appl., 25 (2014), 222-233. doi: 10.1016/j.ffa.2013.09.006.
[33]	C. Mauduit and A. Sárközy, On finite pseudorandom sequences of $k$ symbols, Indag. Math. (N.S.), 13 (2002), 89-101. doi: 10.1016/S0019-3577(02)90008-X.
[34]	W. Meidl and A. Winterhof, Some notes on the linear complexity of Sidelnikov-Lempel-Cohn-Eastman sequences, Des. Codes Cryptogr., 38 (2006), 159-178. doi: 10.1007/s10623-005-6340-2.
[35]	D. Peng and P. Fan, Lower bounds on the Hamming auto- and cross correlations of frequency-hopping sequences, IEEE Trans. Inform. Theory, 50 (2004), 2149-2154. doi: 10.1109/TIT.2004.833362.
[36]	V. M. Sidel'nikov, Some $k$-valued pseudo-random sequences and nearly equidistant codes, Problems Inform. Transmission, 5 (1969), 12-16.
[37]	M. K. Song and H.-Y. Song, Hamming correlation properties of the array structure of Sidelnikov sequences, Des. Codes Cryptogr., 87 (2019), 2537-2551. doi: 10.1007/s10623-019-00636-7.
[38]	V. Tóth, Extension of the notion of collision and avalanche effect to sequences of $k$ symbols, Period. Math. Hungar., 65 (2012), 229-238. doi: 10.1007/s10998-012-1005-1.
[39]	I. M. Vinogradov, Elements of Number Theory, New York: Dover, 1954.
[40]	H. B. Yu, Estimates of character sums with exponential function, Acta Arith., 97 (2001), 211-218. doi: 10.4064/aa97-3-2.
[41]	K. T. Yu, On a trigonometric inequality of Vinogradov, J. Number Theory, 49 (1994), 287-294. doi: 10.1006/jnth.1994.1094.
[42]	N. Y. Yu and G. Gong, New construction of $M$-ary sequence families with low correlation from the structure of Sidelnikov sequences, IEEE Trans. Inform. Theory, 56 (2010), 4061-4070. doi: 10.1109/TIT.2010.2050793.