问Berlekamp-Massey输入序列长度
EN

Cryptography用户

提问于 2021-11-06 11:29:48

回答 2查看 493关注 0票数 1

对于构造最小多项式的给定周期序列的长度为N。Berlekamp-Massey算法是接受2N的输入，即重复输入序列还是仅接受输入序列本身？产生疑问的原因是，通过取长度为N的原序列S \| S和长度2N的序列D4(级联)，我发现最小多项式值会发生变化，但我无法理解为什么最小多项式应该改变。

SageMath

Example 1：

如果我认为这个序列是s=0101110，那么它会重复。然后利用SageMath中的Berlekamp-Massey函数给出了最小多项式x^3+x+1。

代码：

berlekamp_massey([GF(2)(0), 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0])

(这里我必须重复这个序列，因为长度必须是偶数)

Example 2:

如果我认为序列是s=011101，然后它重复，然后在SageMath中使用Berlekamp-Massey函数给出最小多项式x^3+x^2+1。

代码：

berlekamp_massey([GF(2)(0), 1, 1, 1, 0, 1])

(因为长度甚至是berlekamp massey函数都接受这一点)

Example 3:

如果我认为序列是s=011101，那么它就重复；然后在SageMath中使用Berlekamp-Massey函数给出最小多项式x^5+x^4+x^3+x^2+1。

代码：

berlekamp_massey([GF(2)(0), 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1])

(在这里，我故意重复了一遍)

那么，我的问题是如何使用Berlekamp函数实际计算SageMath中序列的线性复杂度？以上哪些例子是正确的，哪些是不正确的？

lfsr

complexity

回答 2

Cryptography用户

发布于 2021-11-06 14:57:50

其中的一个方面是，如果到目前为止，序列(s_t)_{t \geq 0}的计算递归是长度L，则确实需要等到观察2L符号才能验证迄今生成的D2符号是否有效。这是因为系数必须满足矩阵方程\left[\begin{array}{ccccc} s_0 & s_1 & s_2 & \cdots & s_{L-1} \\ s_1 & s_2 & s_3 & \cdots & s_{L} \\ & \vdots & & \vdots & \\ s_{L-1} & s_{L} & s_{L+1} & \cdots & s_{2L-2} \\ \end{array} \right] \left[ \begin{array}{c} c_L \\ c_{L-1} \\ \vdots \\ c_1\end{array} \right] = \left[ \begin{array}{c} s_L \\ s_{L+1} \\ \vdots \\ s_{2L-1}\end{array} \right] 。

其中c_1,\ldots,c_L是特征方程的系数，为了有效。

这是由于重复的性质，它必须继续保持，直到最后一个符号(s_L)的基础上，它的计算不再是矩阵方程的一部分。

票数 2

Cryptography用户

发布于 2021-11-07 01:18:01

给出一个长度为S的2N序列，Berlekamp-Massey算法找到一个产生相同序列S (特别是最短序列)的线性调频随机序列。但是，您不知道序列是否有周期N。您只知道，如果初始状态正确，所产生的序列将等于输入中的序列。所有计算都将在GF(2)中进行。

示例2:具有最小多项式x^3+x^2+1的LFSR是s_{n+3}=s_{n+2}+s_n，我们需要3个初始值来生成sequnce (因为它依赖于s_n和s_{n+2})。在示例中，初始状态为S=011，即s_0=0、s_1=1、s_2=1。您可以看到，下一个值与序列s_3=s_2+s_0=1、s_4=0、s_5=1中的值相同。无论如何，这个序列的周期不是6，所以这个LFSR对于序列S || S不太好(也就是说，如果您继续使用这个LFSR产生位，您将得到一个与S||S不同的序列)。

示例3:这个序列的初始位是相同的，但是这次最短的序列是更复杂的s_{n+5}=s_{n+4}+s_{n+3}+s_{n+2}+s_{n+1}+s_{n}，状态是5位长。当然，如果您在初始状态01110中使用此序列，则第六个位等于示例2中的序列(即位0+1+1+1+0=1)，但是给定初始状态01110，您可以生成序列011101011101。