<abstract xmlns="http://www.w3.org/1999/xhtml"><p>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 <italic>N</italic>th maximum order complexity is of order of magnitude log <italic>N</italic> whereas it is easy to find families of sequences with <italic>N</italic>th expansion complexity exponential in log <italic>N</italic>. 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 <italic>N</italic> th maximum order complexity which are both of the largest possible order of magnitude <italic>N</italic>. 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.</p></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.

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

Uniform distribution theory

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

{"article-title":"On the Maximum Order Complexity of the Thue-Morse and Rudin-Shapiro Sequence"}

Expansion complexity and maximum order complexity are both finer measures of pseudorandomness than the linear complexity which is the most prominent quality...

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

Published Online: Mar 27, 2020

Page range: 33 - 42

Received: May 30, 2018

Accepted: May 17, 2019

DOI: https://doi.org/10.2478/udt-2019-0012

Keywords
Thue-Morse sequence, Rudin-Shapiro sequence, automatic sequences, maximum order complexity, measures of pseudorandomness

© 2019 Zhimin Sun et al., published by Sciendo

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

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

Published Online: Mar 27, 2020

Page range: 33 - 42

Received: May 30, 2018

Accepted: May 17, 2019

DOI: https://doi.org/10.2478/udt-2019-0012

KeywordsThue-Morse sequence, Rudin-Shapiro sequence, automatic sequences, maximum order complexity, measures of pseudorandomness

© 2019 Zhimin Sun et al., published by Sciendo

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

Keywords
Thue-Morse sequence, Rudin-Shapiro sequence, automatic sequences, maximum order complexity, measures of pseudorandomness