Abstract
Let m be a positive integer. We study the linear complexity profile and correlation measure of two interleaved m-ary sequences of length s and t, respectively. In the case that s ≥ 2t or s = t and m is prime we estimate the correlation measure in terms of the correlation measure of the first base sequence and the length of the second base sequence. In this case a relation by Brandstätter and Winterhof immediately implies a lower bound on the linear complexity profile of the interleaved sequence. If m is not a prime, under the same restrictions on s and t, the power correlation measure introduced by Chen and Winterhof takes the role of the correlation measure to obtain lower bounds on the linear complexity profile. Moreover, we show that these restrictions on s and t are necessary, and otherwise the (power) correlation measure can be close to st. However, introducing and estimating the (power) correlation measure with bounded lags we are able to get a lower bound on the linear complexity profile of the interleaved sequence.
Similar content being viewed by others
References
Brandstätter, N., Winterhof, A.: Linear complexity profile of binary sequences with small correlation measure. Period. Math. Hung. 52, 1–8 (2006)
Golomb, S.W., Gong, G.: Signal Design for Good Correlation. Cambridge University Press, Cambridge (2005)
Chen, Z., Winterhof, A.: Linear complexity profile of m-ary pseudorandom sequences with small correlation measure. Indag. Mathem. 20, 631–640 (2011)
Gong, G.: Theory and applications of q-ary interleaved sequences. IEEE Trans. Inform. Theory 41, 400–411 (1995)
Gong, G.: New design for signal sets with low cross-correlation, balance property, and large linear span: GF(p) case. IEEE Trans. Inform. Theory 48, 2847–2867 (2002)
Gyarmati, K.: Measures of pseudorandomness. In: Charpin, P., Pott, A., Winterhof A. (eds.) Finite fields and their applications, 43–64, Radon Ser. Comput. Appl. Math., vol. 11. De Gruyter, Berlin (2013)
He, J.J., Panario, D., Wang, Q.: A family of binary sequences from interleaved construction and their cryptographic properties. Contemp. Math. 518, 209–223 (2010)
Hu, H., Gong, G.: New sequence families with zero or low correlation zone via interleaving techniques. ISIT 2009, Korea, 124–128 (2009)
Mauduit, C., Sárközy, A.: On finite pseudorandom binary sequences, I: Measures of pseudorandomness, the Legendre symbol. Acta Arith 82, 365–377 (1997)
Mauduit, C., Sárközy, A.: On finite pseudorandom sequences of k symbols. Indag. Mathem. 13, 89–101 (2002)
Shparlinski, I.E.: Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness. Progress in Computer Science and Applied Logic, vol. 22. Birkhäuser Verlag, Basel (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
Daniel Panario and Qiang Wang were partially funded by NSERC of Canada. Arne Winterhof was partially supported by the Austrian Science Fund (FWF): Project F5511-N26, which is a part of the Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”. Parts of this paper were written during a very pleasant stay of Arne Winterhof to Carleton University. He wishes to thank for hospitality and financial support.
Rights and permissions
About this article
Cite this article
He, J.J., Panario, D., Wang, Q. et al. Linear complexity profile and correlation measure of interleaved sequences. Cryptogr. Commun. 7, 497–508 (2015). https://doi.org/10.1007/s12095-015-0131-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12095-015-0131-z