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?

Un aspect al acestui lucru este că dacă recurența calculată până acum pentru secvență $(s_t)_{t \geq 0}$ este lungimea $L$, trebuie să așteptați până la observare 2L$ simboluri pentru a verifica dacă LFSR-ul generat până acum este de fapt valid. Acest lucru se datorează faptului că coeficienții trebuie să satisfacă ecuația matriceală $$ \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} și s_{L} și s_{L+1} și \cdots și s_{2L-2} \ \end{matrice} \right] \stânga[ \begin{matrice}{c} c_L \ c_{L-1} \ \vdots \ c_1\end{array} \right] = \stânga[ \begin{matrice}{c} s_L \ s_{L+1} \ \vdots \ s_{2L-1}\end{array} \right] $$

Unde $c_1,\ldots,c_L$ sunt coeficienții ecuației caracteristice, pentru a fi valide.

Acest lucru se datorează naturii suprapuse a recurenței, aceasta trebuie să continue să rămână până la ultimul simbol ($s_L$) pe baza căruia a fost calculată nu mai face parte din ecuația matriceală.

Folosesc codul python al bma.bozhu.me (site-ul nu funcționează recent (problema HTTP), aștept mult timp pentru răspunsuri..)

1. Exemplu: secvența care se repetă $s=(0, 1, 0, 1, 1, 1, 0)$

    secv = (0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0)
    (poli, span) = Berlekamp_Massey_algorithm(seq)
   

   iesiri

   Secvența de intrare este (0, 1, 0, 1, 1, 1, 0). Polinomul său caracteristic este (x^3 + x^1 + 1), iar intervalul liniar este 3.

2. Exemplu: secvența care se repetă $s=(0, 1, 1, 1, 0, 1)$

   secv = (0,1,1,1,0,1)
   (poli, span) = Berlekamp_Massey_algorithm(seq)
   

   Secvența de intrare este (0, 1, 1, 1, 0, 1). Polinomul său caracteristic este (x^3 + x^2 + 1), iar intervalul liniar este 3.

3. Exemplu: secvența care se repetă $s=(0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1)$

   secv = (0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1)
   (poli, span) = Berlekamp_Massey_algorithm(seq)
   

   Secvența de intrare este (0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1). Polinomul său caracteristic este (x^5 + x^4 + x^3 + x^2 + x^1 + 1), iar intervalul liniar este 5.

Da, pare problematic, totuși nu!

Când Belekamp-Massey a produs un rezultat, BM produce un polinom minim. Acest nu înseamnă că se va potrivi cu următoarea ta intrare.

Tine minte, un LFSR de lungime $L$ poate genera o succesiune periodică de lungime $2^L-1$; toate $L$-lungimea șirurilor binare, cu excepția totalului zero. Deci, având o diplomă $3$ înseamnă că un LFSR maxim poate genera o secvență de dimensiune $7$. Secvența periodică reală este $(0, 1, 1, 1, 0, 1,0)$ observați că avem toate triplele cu excepția zero.

Poate exista un LFSR cu polinoame non-primitive care vă pot produce secvențele; acesta nu este jobul lui BM.

Al treilea caz are o problemă similară, lăsată în seama cititorului.

Privind Profilul de complexitate linear

Privind calitatea aleatoriei unei secvențe, este propus și un Profil de complexitate liniară. În acest caz, se dă o secvență și se produce profilul complexității liniare. Rainer A. Rueppel^* a analizat pe larg acest lucru în Analiza și proiectarea Stream Ciphers

Secvența PN este generată de un LFSR, după cum putem vedea, LCP-ul nu crește! (secvențele dvs. au LCP 3 și 5). Aruncarea monedei este cheia înțelegerii;

• atunci când se dă o nouă intrare către BM, dacă etapa curentă o poate produce, complexitatea liniară rămâne aceeași, dacă nu complexitatea liniară este ajustată astfel încât LFST-ul produs să admită și pe cel anterior și pe cel nou.

Asa de, BM produce doar cel mai scurt LFSR pentru partea dată, nu se adresează că următoarea intrare va calcula cu LFSR curent.

Notă: Se pare că SageMath funcționează.

^* Rainer A. Rueppel a fost student al James L. Massey. Se pare că aceasta este prima carte din seria Springer dedicată Criptografiei.

Dată o secvență $S$ de lungime 2 N$ algoritmul Berlekamp-Massey găsește un LFSR care produce aceeași secvență $S$ (în special este cea mai scurtă). Dar, nu știi dacă secvența are punct $N$. Știți doar că, cu starea inițială corectă, secvența produsă va fi egală cu cea din intrare. Toate calculele vor fi în $GF(2)$.

Exemplul 2: LFSR cu polinom minim $x^3+x^2+1$ este $s_{n+3}=s_{n+2}+s_n$ și avem nevoie de 3 valori inițiale pentru a produce o secvență (pentru că depinde de $s_n$ și $s_{n+2}$). În exemplu, starea inițială este $S=011$, acesta este $s_0=0$, $s_1=1$, $s_2=1$. Puteți vedea că următoarele valori sunt aceleași ca în secvență $s_3=s_2+s_0=1$, $s_4=0$, $s_5=1$. Oricum, perioada acestei secvențe nu este 6 și deci acest LFSR nu este bine pentru secvență $S || S$ (adică dacă continuați să produceți biți cu acest LFSR, veți obține o secvență care este diferită de $S||S$).

Exemplul 3: biții inițiali ai acestei secvențe sunt aceiași, dar de data aceasta cea mai scurtă secvență este mai complexă $s_{n+5}=s_{n+4}+s_{n+3}+s_{n+2}+s_{n+1}+s_{n}$ iar statul este $5$ biți lungi. Sigur dacă utilizați această secvență cu starea inițială $01110$ al șaselea bit este egal cu secvența din exemplul 2 (adică bit $0+1+1+1+0=1$) dar dată fiind starea inițială $01110$ puteți produce secvența $011101011101$.