Abstract
In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography) it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated.
Similar content being viewed by others
REFERENCES
R. Ahlswede, Coloring hypergraphs: A new approach to multi-user source coding, Part I, Journ. of Combinatorics, Information and System Sciences, 4, No. 1 (1979), 76–115; Part II, Journ. of Combinatorics, Information and System Sciences, 5, No. 3 (1980), 220–268.
J. Cassaigne, C. Mauduit and A. SÁrközy, On finite pseudorandom binary sequences VII: The measures of pseudorandomness, Acta Arith. (to appear).
L. Goubin, C. Mauduit and A. SÁrkÖzy, Construction of large families of pseudorandom binary sequences, J. Number Theory (to appear).
C. Mauduit and A. SÁrkÖzy, On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol, Acta Arith. 82, (1997), 365–377.
C. Mauduit and A. SÁrkÖzy, On finite pseudorandom sequences of k symbols, Indagationes Math. (to appear).
U. maurer and J. L. Massey, Local randomness in pseudorandom sequences, J. Cryptology 4 (1991), 135–149.
A. SÁrkÖzy, A finite pseudorandom binary sequence, Studia Sci. Math. Hungar. 38 (2001), 377–384.
C. P. Schnorr, On the construction of random number generators and random function generators, Advances in Cryptology – EUROCRYPT' 88 (LNCS 330), 1988, 225–232.
A. Weil, Sur les courbes algébriques et les variétés qui s'en déduisent, Act. Sci. Ind. 1041, Hermann, Paris, 1948.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ahlswede, R., Khachatrian, L.H., Mauduit, C. et al. A complexity measure for families of binary sequences. Periodica Mathematica Hungarica 46, 107–118 (2003). https://doi.org/10.1023/A:1025962825241
Issue Date:
DOI: https://doi.org/10.1023/A:1025962825241