1. bookVolume 15 (2020): Issue 2 (December 2020)
Journal Details
License
Format
Journal
eISSN
2309-5377
First Published
30 Dec 2013
Publication timeframe
2 times per year
Languages
English
access type Open Access

On the Maximum Order Complexity of Thue–Morse and Rudin–Shapiro Sequences along Polynomial Values

Published Online: 25 Dec 2020
Volume & Issue: Volume 15 (2020) - Issue 2 (December 2020)
Page range: 9 - 22
Received: 17 Jun 2020
Accepted: 24 Jun 2020
Journal Details
License
Format
Journal
eISSN
2309-5377
First Published
30 Dec 2013
Publication timeframe
2 times per year
Languages
English
Abstract

Both the Thue–Morse and Rudin–Shapiro sequences are not suitable sequences for cryptography since their expansion complexity is small and their correlation measure of order 2 is large. These facts imply that these sequences are highly predictable despite the fact that they have a large maximum order complexity. Sun and Winterhof (2019) showed that the Thue–Morse sequence along squares keeps a large maximum order complexity. Since, by Christol’s theorem, the expansion complexity of this rarefied sequence is no longer bounded, this provides a potentially better candidate for cryptographic applications. Similar results are known for the Rudin–Shapiro sequence and more general pattern sequences. In this paper we generalize these results to any polynomial subsequence (instead of squares) and thereby answer an open problem of Sun and Winterhof. We conclude this paper by some open problems.

Keywords

MSC 2010

[1] ALLOUCHE, J.-P.—SHALLIT, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003.10.1017/CBO9780511546563Search in Google Scholar

[2] ALON, N.—KOHAYAKAWA, Y.—MAUDUIT, C.—MOREIRA, C. G.—RÖDL, V.: Measures of pseudorandomness for finite sequences: typical values, Proc. Lond. Math. Soc. (3) 95 (2007), 778–812.10.1112/plms/pdm027Search in Google Scholar

[3] CHRISTOL, G.: Ensembles presque periodiques k-reconnaissables, Theoret. Comput. Sci. 9 (1979), 141–145.10.1016/0304-3975(79)90011-2Search in Google Scholar

[4] 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

[5] DRMOTA, M.—MAUDUIT, C.—RIVAT, J.: The sum-of-digits function of polynomial sequences, J.Lond. Math. Soc.(2) 84 (2011), 81–102.10.1112/jlms/jdr003Search in Google Scholar

[6] DRMOTA, M.—MAUDUIT, C.—RIVAT, J.: Normality along squares, J. Eur. Math. Soc. (JEMS) 21 (2019), 507–548.10.4171/JEMS/843Search in Google Scholar

[7] MAUDUIT, C.—RIVAT, J.: Rudin–Shapiro sequences along squares, Transactions of the Amer. Math. Soc. 370 (2018), 7899–7921.10.1090/tran/7210Search in Google Scholar

[8] 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

[9] 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

[10] 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

[11] MOSHE, Y.: On the subword complexity of Thue-Morse polynomial extractions, Theoret. Comput. Sci. 389 (2007), 318–329.10.1016/j.tcs.2007.10.015Search in Google Scholar

[12] MÜLLNER, C.: The Rudin-Shapiro sequence and similar sequences are normal along squares, Canad. J. Math. 70 (2018), 1096–1129.10.4153/CJM-2017-053-1Search in Google Scholar

[13] SUN, Z.—WINTERHOF, A.: On the maximum order complexity of subsequences of the Thue-Morse and Rudin-Shapiro sequence, Unif. Distrib. Theory 14 (2019), 33–42.10.2478/udt-2019-0012Search in Google Scholar

[14] 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

Recommended articles from Trend MD

Plan your remote conference with Sciendo