<abstract xmlns="http://www.w3.org/1999/xhtml"><p>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.</p></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.

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

Uniform distribution theory

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Both the Thue–Morse and Rudin–Shapiro sequences are not suitable sequences for cryptography since their expansion complexity is small and their correlation...

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

Published Online: Dec 25, 2020

Page range: 9 - 22

Received: Jun 17, 2020

Accepted: Jun 24, 2020

DOI: https://doi.org/10.2478/udt-2020-0008

Keywords
Automatic sequences, pseudorandomness, Thue–Morse sequence, Rudin–Shapiro sequence, polynomials

© 2020 Pierre Popoli, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

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

Published Online: Dec 25, 2020

Page range: 9 - 22

Received: Jun 17, 2020

Accepted: Jun 24, 2020

DOI: https://doi.org/10.2478/udt-2020-0008

KeywordsAutomatic sequences, pseudorandomness, Thue–Morse sequence, Rudin–Shapiro sequence, polynomials

© 2020 Pierre Popoli, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Keywords
Automatic sequences, pseudorandomness, Thue–Morse sequence, Rudin–Shapiro sequence, polynomials