文章/答案/技术大牛

发布

社区首页 >问答首页 >是否有一种方法可以使序列的线性复杂度小于其周期？

问是否有一种方法可以使序列的线性复杂度小于其周期？
EN

Cryptography用户

提问于 2021-02-25 08:03:09

回答 1查看 55关注 0票数 3

有限域上序列s_0,s_1,\ldots的线性复杂度是序列线性递推的最短长度n

s_{n+j}=\sum_{i=0}^{n-1}a_is_{i+j}

对于字段中的常量j=0,1,2,\ldots，a_i。我的问题是，我们应该在哪一个n上停止计算a_i？假设序列周期为周期N，那么在哪个n处，我们应该停止对上述递推关系中系数的搜索，以便该关系对所有后续的较长序列都有效，直到整个周期为止？

这个定义似乎没有给出任何计算线性复杂性的清晰概念。即使是Berlekamp Massey算法也没有说在n小于N的情况下停止什么。

pseudo-random-generator

lfsr

回答 1

Cryptography用户

发布于 2021-02-25 09:49:07

我的问题是，我们应该在哪一个n上停止计算a_i？假设序列是周期的N，在哪n处我们应该停止对上述递推关系中的系数的搜索，这样这种关系在整个周期之前对所有后续的较长序列都是有效的？

如果序列是周期的，则序列的线性复杂度在某一点之后不会发生变化。请记住，如果最小多项式是最大的，具有长度L的LFSR可以产生最大长度2^L-1的周期序列。

但是Berlakamp- all算法不能检测周期，它必须处理所有的输入.它以交互的方式工作，以便在一个新位无法与输出相匹配时更新内部，即存在差异。一旦达到周期，它将不会更新内部，但算法只能修改，以输出最后修改的内部距离。

如果您知道周期，则可以在处理N位后停止Berlakamp。原因可以看作是在下一个极端的例子。考虑周期序列，在周期中，它有99-0，然后是1。

\overbrace{\underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}}^{\text{ the preiod}}\, \underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}\cdots \underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}\cdots

该序列的线性复杂度为100。因此，您必须处理所有的周期，以找到序列的线性复杂性。

这个定义似乎没有给出任何计算线性复杂度的清晰概念。即使是Berlekamp Massey算法也没有说在n小于N的情况下停止

因为它是为产生产生给定序列的LFSR而设计的，所以仅此而已。如前所述，它必须处理所有的输入。

如果要查找周期，请使用像Z-算法这样的周期查找算法

票数 3

页面原文内容由Cryptography提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://crypto.stackexchange.com/questions/88474

复制

相似问题

问是否有一种方法可以使序列的线性复杂度小于其周期？
EN

回答 1

Cryptography用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问是否有一种方法可以使序列的线性复杂度小于其周期？EN

回答 1

Cryptography用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问是否有一种方法可以使序列的线性复杂度小于其周期？
EN