×

Linear complexity of periodically repeated random sequences. (English) Zbl 0841.60023

Summary: On the linear complexity \(\Lambda(\widetilde{z})\) of a periodically repeated random bit sequence \(\widetilde{z}\), R. A. Rueppel proved that, for two extreme cases of the period \(T\), the expected linear complexity \(E[\Lambda(\widetilde{z})]\) is almost equal to \(T\), and suggested that \(E[\Lambda(\widetilde{z})]\) would be close to \(T\) in general [“New approaches to stream ciphers” (PhD diss., Zürich, 1984); in: Advances in cryptology – EUROCRYPT 1985. Lect. Notes Comput. Sci. 219, 167–188 (1986); and “Analysis and design of stream ciphers.” Berlin etc.: Springer- Verlag (1986; Zbl 0618.94001)]. We obtain exact formulas and bounds of \(E[\Lambda(\widetilde{z})]\), as well as formulas and bounds of the variance \(\text{Var}[\Lambda(\widetilde{z})]\), both for the general case of \(T\), and we estimate the probability distribution of \(\Lambda(\widetilde{z})\). Our results on \(E[\Lambda(\widetilde{z})]\) quantify the closeness of \(E[\Lambda(\widetilde{z})]\) and \(T\), and in particular, formally confirm Rueppel’s suggestion.

MSC:

94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Zhang, M.R.,Embedding flows and functional equations, Acta Math. Sinica (New Series),8(1992), 148–157. · Zbl 0757.58035 · doi:10.1007/BF02629935
[2] Zhang, M.R. & Li, W.G.,One dimensional dynamics: adopting embedding flow method, Advances Math. (China),21(1992), 245–246.
[3] Kopell, N.,Commuting diffeomorphisms, inGlobal Analysis, AMS Proc. Symp. Pure Math.,14(1970), 165–184. · doi:10.1090/pspum/014/0270396
[4] Palis, J. & Yoccoz, J.C.,Rigidity of centralizers of diffeomorphisms, Ann. Sci. Ec. Norm. Sup.,22(1989), 81–98. · Zbl 0709.58022 · doi:10.24033/asens.1576
[5] Anosov, D.V. & Arnold, V.I.,Dynamical Systems I, Springer-Verlag, Berlin, 1988, 92–96.
[6] Zhang, M.R.,Classification of C 1 diffeomorphisms of the real line under C 1 conjugacy, Chin. Sci. Bull.,38(1993), 1145–1149. · Zbl 0802.58049
[7] Nitecki, Z.,Differentiable Dynamics, MIT Press, Cambridge, 1971. · Zbl 0246.58012
[8] Yoccoz, J.C.,Centralisateurs et conjugaison différentiable des difféomorphisms du cercle, to appear in Astérisque.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.