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

[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-1Search in Google Scholar

[2] BRIDY, A.: Automatic sequences and curves over finite fields, Algebra Number Theory 11 (2017), 685–712.10.2140/ant.2017.11.685Search in Google Scholar

[3] DIEM, C.: On the use of expansion series for stream ciphers, LMS J. Comput. Math. 15 (2012), 326–340.10.1112/S146115701200109XSearch in Google Scholar

[4] ERDMANN, D.—MURPHY, S.: An approximate distribution for the maximum order complexity, Des. Codes Cryptogr. 10 (1997), 325–339.10.1023/A:1008295603824Search in Google Scholar

[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.0204Search in Google Scholar

[6] IŞIK, L.—WINTERHOF, A.: Maximum-order complexity and correlation measures, Cryptography 1 (2017), no. 7, 1–5.10.3390/cryptography1010007Search in Google Scholar

[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

[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_13Search in Google Scholar

[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_10Search in Google Scholar

[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.907442Search in Google Scholar

[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.2736545Search in Google Scholar

[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-377Search in Google Scholar

[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.2286Search in Google Scholar

[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

[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-2Search in Google Scholar

[16] MÉRAI, L.—WINTERHOF, A.: On the pseudorandomness of automatic sequences, Cryptogr. Commun. 10 (2018), 1013–1022.10.1007/s12095-017-0260-7Search in Google Scholar

[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.008Search in Google Scholar

[18] NIEDERREITER, H.—XING, C.: Sequences with high nonlinear complexity, IEEE Trans. Inform. Theory 60 (2014), 6696–6701.10.1109/TIT.2014.2343225Search in Google Scholar

[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.1566275Search in Google Scholar

[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.2714681Search in Google Scholar