Abstract.
We prove a conjecture on the asymptotic behavior of the joint linear complexity profile of random multisequences over a finite field. This conjecture was previously shown only in the special cases of single sequences and pairs of sequences. We also establish an asymptotic formula for the expected value of the nth joint linear complexity of random multisequences over a finite field. Some more precise results are shown for triples of sequences.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
TW Cusick C Ding A Renvall (1998) Stream Ciphers and Number Theory Elsevier Amsterdam Occurrence Handle0930.11086
Dai ZD, Imamura K, Yang JH (2005) Asymptotic behavior of normalized linear complexity of multi-sequences. In: Helleseth T, Sarwate D, Song H-Y (eds) Sequences and Their Applications – SETA 2004. Lect Notes Computer Science 3486: 129–142. Berlin Heidelberg New York: Springer
Ding C, Xiao G, Shan W (1991) The Stability Theory of Stream Ciphers. Lect Notes Computer Science 561. Berlin Heidelberg New York: Springer
Feng XT, Dai ZD (2005) Expected value of the linear complexity of two-dimensional binary sequences. In: Helleseth T, Sarwate D, Song H-Y (eds) Sequences and Their Applications – SETA 2004. Lect Notes Computer Science 3486: 113–128. Berlin Heidelberg New York: Springer
XT Feng QL Wang ZD Dai (2005) ArticleTitleMulti-sequences with d-perfect property J Complexity 21 230–242 Occurrence Handle10.1016/j.jco.2004.04.004 Occurrence Handle2123225 Occurrence Handle1075.68024
F-W Fu H Niederreiter M Su (2005) ArticleTitleThe expectation and variance of the joint linear complexity of random periodic multisequences J Complexity 21 804–822 Occurrence Handle10.1016/j.jco.2005.07.001 Occurrence Handle2182446 Occurrence Handle1092.94022
FG Gustavson (1976) ArticleTitleAnalysis of the Berlekamp-Massey linear feedback shift-register synthesis algorithm IBM J Res Develop 20 204–212 Occurrence Handle416765 Occurrence Handle10.1147/rd.203.0204 Occurrence Handle0351.94021
R Lidl H Niederreiter (1997) Finite Fields Cambridge Univ Press Cambridge
M Loève (1963) Probability Theory EditionNumber3 Van Nostrand New York Occurrence Handle0108.14202
Meidl W (2005) Discrete Fourier transform, joint linear complexity and generalized joint linear complexity of multisequences. In: Helleseth T, Sarwate D, Song H-Y (eds) Sequences and Their Applications – SETA 2004. Lect Notes Computer Science 3486: 101–112. Berlin Heidelberg New York: Springer
W Meidl H Niederreiter (2003) ArticleTitleThe expected value of the joint linear complexity of periodic multisequences J Complexity 19 61–72 Occurrence Handle10.1016/S0885-064X(02)00009-2 Occurrence Handle1951323 Occurrence Handle1026.68067
W Meidl A Winterhof (2005) ArticleTitleOn the joint linear complexity profile of explicit inversive multisequences J Complexity 21 324–336 Occurrence Handle10.1016/j.jco.2004.09.001 Occurrence Handle2138443 Occurrence Handle1094.94023
Niederreiter H (1988) The probabilistic theory of linear complexity. In: Günther CG (ed) Advances in Cryptology – EUROCRYPT’88. Lect Notes Computer Science 330: 191–209. Berlin Heidelberg New York: Springer
Niederreiter H (2003) Linear complexity and related complexity measures for sequences. In: Johansson T, Maitra S (eds) Progress in Cryptology – INDOCRYPT 2003. Lect Notes Computer Science 2904: 1–17. Berlin Heidelberg New York: Springer
H Niederreiter CP Xing (2001) Rational Points on Curves over Finite Fields: Theory and Applications Cambridge Univ Press Cambridge Occurrence Handle0971.11033
RA Rueppel (1986) Analysis and Design of Stream Ciphers Springer Berlin Heidelberg New York Occurrence Handle0618.94001
RA Rueppel (1992) Stream ciphers GJ Simmons (Eds) Contemporary Cryptology: The Science of Information Integrity IEEE Press New York 65–134
Wang L-P, Niederreiter H (2005) Enumeration results on the joint linear complexity of multisequences. Finite Fields Appl (to appear); available online as document doi:10.1016/j.ffa.2005.03.005
L-P Wang Y-F Zhu D-Y Pei (2004) ArticleTitleOn the lattice basis reduction multisequence synthesis algorithm IEEE Trans Inform Theory 50 2905–2910 Occurrence Handle10.1109/TIT.2004.836670 Occurrence Handle2097012 Occurrence Handle1178.94181
CP Xing (2000) ArticleTitleMulti-sequences with almost perfect linear complexity profile and function fields over finite fields J Complexity 16 661–675 Occurrence Handle10.1006/jcom.2000.0560 Occurrence Handle1801588 Occurrence Handle1026.94006
Xing CP, Lam KY, Wei ZH (1999) A class of explicit perfect multi-sequences. In: Lam KY, Okamoto E, Xing CP (eds) Advances in Cryptology – ASIACRYPT’99. Lect Notes Computer Science 1716: 299–305. Berlin Heidelberg New York: Springer
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Niederreiter, H., Wang, LP. The Asymptotic Behavior of the Joint Linear Complexity Profile of Multisequences. Mh Math 150, 141–155 (2007). https://doi.org/10.1007/s00605-005-0392-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00605-005-0392-2