Skip to Main content Skip to Navigation
Journal articles

On The Maximum Order Complexity Of Thue-Morse And Rudin-Shapiro Sequences Along Polynomial Values

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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.univ-lorraine.fr/hal-02944612
Contributor : Pierre Popoli <>
Submitted on : Monday, September 21, 2020 - 3:36:24 PM
Last modification on : Monday, May 17, 2021 - 3:42:09 PM
Long-term archiving on: : Friday, December 4, 2020 - 5:06:04 PM

File

Article Popoli UDT.pdf
Files produced by the author(s)

Identifiers

Citation

Pierre Popoli. On The Maximum Order Complexity Of Thue-Morse And Rudin-Shapiro Sequences Along Polynomial Values. Uniform Distribution Theory, Mathematical Institute of the Slovak Academy of Sciences, In press, ⟨10.2478/udt-2020-0008⟩. ⟨hal-02944612⟩

Share

Metrics

Record views

131

Files downloads

82