On the Maximum Order Complexity of the Thue-Morse and Rudin-Shapiro Sequence

Zhimin Sun; Arne Winterhof

doi:10.2478/udt-2019-0012

Abstract

Expansion complexity and maximum order complexity are both finer measures of pseudorandomness than the linear complexity which is the most prominent quality measure for cryptographic sequences. The expected value of the Nth maximum order complexity is of order of magnitude log N whereas it is easy to find families of sequences with Nth expansion complexity exponential in log N. This might lead to the conjecture that the maximum order complexity is a finer measure than the expansion complexity. However, in this paper we provide two examples, the Thue-Morse sequence and the Rudin-Shapiro sequence with very small expansion complexity but very large maximum order complexity. More precisely, we prove explicit formulas for their N th maximum order complexity which are both of the largest possible order of magnitude N. We present the result on the Rudin-Shapiro sequence in a more general form as a formula for the maximum order complexity of certain pattern sequences.

References

[1] BRANDSTÄTTER, N.—WINTERHOF, A.: Linear complexity profile of binary sequences with small correlation measure, Period. Math. Hungar. 52 (2006), 1–8.10.1007/s10998-006-0008-1
Search in Google Scholar Back to article
[2] BRIDY, A.: Automatic sequences and curves over finite fields, Algebra Number Theory 11 (2017), 685–712.10.2140/ant.2017.11.685
Search in Google Scholar Back to article
[3] DIEM, C.: On the use of expansion series for stream ciphers, LMS J. Comput. Math. 15 (2012), 326–340.10.1112/S146115701200109X
Search in Google Scholar Back to article
[4] ERDMANN, D.—MURPHY, S.: An approximate distribution for the maximum order complexity, Des. Codes Cryptogr. 10 (1997), 325–339.10.1023/A:1008295603824
Search in Google Scholar Back to article
[5] GUSTAVSON, F. G.: Analysis of the Berlekamp-Massey linear feedback shift-register synthesis algorithm,IBM J. Res. Develop. 20 (1976), 204–212.10.1147/rd.203.0204
Search in Google Scholar Back to article
[6] IŞIK, L.—WINTERHOF, A.: Maximum-order complexity and correlation measures, Cryptography 1 (2017), no. 7, 1–5.10.3390/cryptography1010007
Search in Google Scholar Back to article
[7] JANSEN, C.J.A.: Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods, Ph.D. Dissertation, Technical University of Delft, Delft, 1989.
Search in Google Scholar Back to article
[8] JANSEN, C. J. A.: The maximum order complexity of sequence ensembles,In: Advances in Cryptology—EUROCRYPT ’91 (D. W. Davies, ed.), Lecture Notes in Comput. Sci. Vol. 547, Springer-Verlag, Berlin, 1991, pp. 153–159.10.1007/3-540-46416-6_13
Search in Google Scholar Back to article
[9] JANSEN, C. J. A.—BOEKEE; D. E.: The shortest feedback shift register that can generate a given sequence, In: Advances in Cryptology—CRYPTO (G. Brassard, ed.), Lecture Notes in Comput. Sci. Vol. 435, Springer-Verlag, Berlin Heidelberg, 1990, pp. 90–99,10.1007/0-387-34805-0_10
Search in Google Scholar Back to article
[10] LIMNIOTIS, K.—KOLOKOTRONIS, N.—KALOUPTSIDIS, N.: On the nonlinear complexity and Lempel-Ziv complexity of finite length sequences, IEEE Trans. Inform. Theory 53 (2007), 4293–4302.10.1109/TIT.2007.907442
Search in Google Scholar Back to article
[11] LUO, Y. —XING, C.—YOU, L.: Construction of sequences with high nonlinear complexity from function fields, IEEE Trans. Inform. Theory 63 (2017), 7646–7650..10.1109/TIT.2017.2736545
Search in Google Scholar Back to article
[12] MAUDUIT, C.—SÁRKÖZY, A.: On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol,Acta Arith. 82 (1997), 365–377.10.4064/aa-82-4-365-377
Search in Google Scholar Back to article
[13] MAUDUIT, C.—SÁRKÖZY, A.: On finite pseudorandom binary sequences: II. The Champernowne, Rudin-Shapiro, and Thue-Morse sequences, a further construction,J. Number Theory 73 (1998), 256–276.10.1006/jnth.1998.2286
Search in Google Scholar Back to article
[14] MEIDL, W. —WINTERHOF, A.: Linear complexity of sequences and multisequences.In: Handbook of finite fields (G. L. Mullen, D. Panario, eds.), CRC Press, Boca Raton, FL, 2013, 324–336.
Search in Google Scholar Back to article
[15] MÉRAI, L.—NIEDERREITER, H.—WINTERHOF, A.: Expansion complexity and linear complexity of sequences over finite fields, Cryptogr. Commun. 9 (2107), 501–509.10.1007/s12095-016-0189-2
Search in Google Scholar Back to article
[16] MÉRAI, L.—WINTERHOF, A.: On the pseudorandomness of automatic sequences, Cryptogr. Commun. 10 (2018), 1013–1022.10.1007/s12095-017-0260-7
Search in Google Scholar Back to article
[17] MÉRAI, L.—WINTERHOF, A.: On the Nth linear complexity of automatic sequences, J. Number Theory 187 (2018), 415–429.10.1016/j.jnt.2017.11.008
Search in Google Scholar Back to article
[18] NIEDERREITER, H.—XING, C.: Sequences with high nonlinear complexity, IEEE Trans. Inform. Theory 60 (2014), 6696–6701.10.1109/TIT.2014.2343225
Search in Google Scholar Back to article
[19] SUN, Z.—WINTERHOF, A.: On the maximum order complexity of subsequences of the Thue-Morse and Rudin-Shapiro sequence along squares,Int.J.Comput.Math. Comput. Syst. Theory 4 (2019), 30–36.10.1080/23799927.2019.1566275
Search in Google Scholar Back to article
[20] SUN, Z.—ZENG, Z.—LI, C.—HELLESETH, T.: Investigations on periodic sequences with maximum nonlinear complexity, IEEE Trans. Inform. Theory 63 (2017), 6188–6198.10.1109/TIT.2017.2714681
Search in Google Scholar Back to article

On the Maximum Order Complexity of the Thue-Morse and Rudin-Shapiro Sequence

Abstract

Paradigm

My account