Berlekamp–Massey input sequence length

For a given periodic sequence of length $N$ for which minimal polynomial is being constructed. Does the Berlekamp-Massey algorithm take the input of $2N$, i.e., the repeated input sequence or just the input sequence itself? The doubt arise because by taking the original sequence $S$ of length $N$, and the sequence $S \| S$ (concatenation) of length $2N$, I found that the minimal polynomial value changes but I am unable to understand why the minimal polynomial should change.

SageMath

Example 1:

If I consider the sequence to be s=0101110 and then it repeats. Then by using Berlekamp–Massey function in SageMath gives the minimal polynomial $$x^3+x+1$$

code:

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

(Here I have to repeat the sequence because the length must be even)

Example 2:

If I consider the sequence to be s=011101 and then it repeats then by using Berlekamp–Massey function in SageMath gives the minimal polynomial $$x^3+x^2+1$$

code:

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

(since the length is even the berlekamp massey function accepts this)

Example 3:

If I consider the sequence to be s=011101 and then it repeats; then by using Berlekamp–Massey function in SageMath gives the minimal polynomial $$x^5+x^4+x^3+x^2+1$$

code:

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

(Here I intentionally repeated this)

So, My question is how to actually compute the linear complexity of sequence in SageMath using Berlekamp–Massey function? which of the above examples are correct and which are incorrect?

One aspect of this is that if the so far computed recurrence for the sequence $(s_t)_{t \geq 0}$ is length $L$, you do need to wait until observing $2L$ symbols to verify that the LFSR so far generated is actually valid. This is because the coefficients must satisfy the matrix equation $$ \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] $$

where $c_1,\ldots,c_L$ are the coefficients of the characteristic equation, in order to be valid.

This is due to the overlapping nature of the recurrence, it must continue to hold until the last symbol ($s_L$) based on which it was computed is no longer part of the matrix equation.

I'm using the python code of bma.bozhu.me (site not working recently (HTTP problem), waiting a long time for answers..)

1. Example : The repeating sequence $s=(0, 1, 0, 1, 1, 1, 0)$

    seq = (0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0)
    (poly, span) = Berlekamp_Massey_algorithm(seq)
   

   outputs

   The input sequence is (0, 1, 0, 1, 1, 1, 0). Its characteristic polynomial is (x^3 + x^1 + 1), and linear span is 3.

2. Example: The repeating sequence $s=(0, 1, 1, 1, 0, 1)$

   seq = (0,1,1,1,0,1)
   (poly, span) = Berlekamp_Massey_algorithm(seq)
   

   The input sequence is (0, 1, 1, 1, 0, 1). Its characteristic polynomial is (x^3 + x^2 + 1), and linear span is 3.

3. Example : The repeating sequence $s=(0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1)$

   seq = (0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1)
   (poly, span) = Berlekamp_Massey_algorithm(seq)
   

   The input sequence is (0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1). Its characteristic polynomial is (x^5 + x^4 + x^3 + x^2 + x^1 + 1), and linear span is 5.

Yes, it seems problematic, however, not!

When Belekamp-Massey produced a result, BM produce a minimal polynomial. This doesn't mean that it will match your next input.

Remember, an LFSR of length $L$ can generate a periodic sequence of length $2^L-1$; all $L$-length binary strings except the all-zero. So, having a degree $3$ means, a maximal LFSR can generate a sequence of size $7$. The actual periodic sequence is $(0, 1, 1, 1, 0, 1,0)$ notice that we have all triples except zero.

There can be an LFSR with non-primitive polynomials that can produce your sequences; this is not the Job of BM.

The third case has a similar problem, left to the reader.

Looking at Linear Complexity Profile

Looking at the quality of the randomness of a sequence, a Linear Complexity Profile is also proposed. In this case, a sequence is given and the profile of linear complexity is produced. Rainer A. Rueppel^* extensively analyzed this in Analysis and Design of Stream Ciphers

The PN-sequnce is generated by an LFSR, as we can see, the LCP doesn't grow! ( your sequences has LCP 3 and 5). The coin tossing is the key to understanding;

• when a new input is given to BM, if the current stage can produce it, the linear complixy stays the same, if not the linear complexity is adjusted so that the produced LFST admits the previous and the new one, too.

So, BM only produces shortest LFSR to the given part, it is not adressing that the next input will math with the current LFSR.

Note: It Seems SageMath is working.

^* Rainer A. Rueppel was a student of James L. Massey. It seems this is the first book in the Springer series devoted to Cryptography.

Given a sequence $S$ of length $2N$ the Berlekamp-Massey algorithm finds an LFSR which produces the same sequence $S$ (in particular it is the shortest one). But, you don't know if the sequence has the period $N$. You only know that with the correct initial state, the sequence produced will be equal to the one in input. All computations will be in $GF(2)$.

Example 2: the LFSR with minimal polynomial $x^3+x^2+1$ is $s_{n+3}=s_{n+2}+s_n$ and we need 3 initial values to produce a sequnce (because it depends on $s_n$ and $s_{n+2}$). In the example the initial state is $S=011$, that is $s_0=0$, $s_1=1$, $s_2=1$. You can see that the next values are the same as in the sequence $s_3=s_2+s_0=1$, $s_4=0$, $s_5=1$. Anyway the period of this sequence is not 6 and so this LFSR is not fine for the sequence $S || S$ (that is if you go on producing bits with this LFSR you will obtain a sequence which is different from $S||S$).

Example 3: the initial bits of this sequence are the same, but this time the shortest sequence is more complex $s_{n+5}=s_{n+4}+s_{n+3}+s_{n+2}+s_{n+1}+s_{n}$ and the state is $5$ bits long. Sure if you use this sequence with initial state $01110$ the sixth bit is equal to the sequence in example 2 (that is the bit $0+1+1+1+0=1$) but given the initial state $01110$ you can produce the sequence $011101011101$.