1
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ Note that an LFSR of length $L$ can produce a sequence of length $2^L-1$ ( if maximal). In this case, the Berlekamp Massey requires only $2L$ output to construct the LFSR (length and taps) and the initial value. Now can you solve your problem? ( It is all about finding the minimal LFSR that can generate this sequence and after that, it repeats...). You should be very carefull about concatenating. $\endgroup$
    – kelalaka
    Nov 6, 2021 at 19:34
  • $\begingroup$ I have added some of my work which I am trying to understand go through since morning. My actual doubt is lying in how to compute linear complexity of sequence correctly using SAGEMATH software and why SAGEMATH forces even length inputs. $\endgroup$ Nov 6, 2021 at 20:13
  • $\begingroup$ Repeating the sequence is not the same as extending it. Repeating increases the linear complexity, while extending (using the minimal poly it satisfies) does not. $\endgroup$
    – Fractalice
    Nov 7, 2021 at 9:04

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Okay, then regarding examples 2 and 3, which of them is the correct minimal polynomial for the generation of the sequence s=011101, from what I understood from this answer is latter, right? $\endgroup$ Nov 7, 2021 at 3:21
2
$\begingroup$

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

enter image description here

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.

$\endgroup$
1
  • $\begingroup$ Is it possible that the minimal polynomial constructed by the berlekamp massey algorithm in SAGEMATH is not the actual minimal polynomial, otherwise the minimal polynomial shouldn't change from example 2 to example 3 just by repeating the periodic sequence? Also to confirm between example 2 and 3, which will be considered the correct minimal polynomial of given sequence s? $\endgroup$ Nov 7, 2021 at 7:26
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.