论文标题
关于沿多项式的thue-morse和rudin-shapiro序列的最大级数复杂性
On the maximum order complexity of Thue-Morse and Rudin-Shapiro sequences along polynomial values
论文作者
论文摘要
Thue-Morse和Rudin-Shapiro序列都不适合密码学序列，因为它们的膨胀复杂性很小，并且其相关度级别2很大。这些事实表明，尽管这些序列具有较大的最大订单复杂性，但这些序列是可以预测的。 Sun和Winterhof（2019）表明，沿正方形的thue-morse序列保持较大的最大订单复杂性。由于Christol的定理不再界定这个稀有序列的扩展复杂性，因此为加密应用提供了更好的候选者。类似的结果是鲁丁 - 射精序列和更通用的模式序列已知的。在本文中，我们将这些结果推广到任何多项式子序列（而不是正方形），从而回答了阳光和温特霍夫的开放问题。我们通过一些开放问题总结了本文。
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.
