序列的預期線性複雜度

令 (s) 為長度為 n 的序列。(s) 和的預期線性複雜度是多少？ $ (s)^{\infty} $ （意味著 s 的周期性版本）？

我不知道這個問題的答案？當它說：“預期的線性複雜度”是什麼意思？有人對這個問題有任何想法嗎？

請注意：對於滿足 Golomb 隨機性假設的序列，我們計算序列的“線性複雜度輪廓”，並且對於此類序列，證明每一步的線性複雜度大約等於 n/2。實際上，LC 值在 n/2 線的 +(-)5/18 附近。但在上述問題中，沒有關於序列隨機性的規範。

這意味著（通常）對給定長度的所有序列進行平均。Rueppel 在他的書中計算了這一點。

這是一個獨立同分佈的統一序列，命題 4.6。作為 $ n $ 根據大數定律，該樣本均值趨近於實際均值。

很久以後，Meidl 和 Niederreiter 嚴格證明了這一點。在付費牆後面，但您可以看到下面的摘要：

https://ieeexplore.ieee.org/abstract/document/1042274/

答案差不多 $ n $ 為了 $ n $ - 週期性序列。

引用自：https://crypto.stackexchange.com/questions/61602