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?

Một khía cạnh của điều này là nếu tính toán lặp lại cho đến nay cho chuỗi $(s_t)_{t \geq 0}$ là chiều dài $L$, bạn cần đợi cho đến khi quan sát $2L$ để xác minh rằng LFSR được tạo cho đến nay thực sự hợp lệ. Điều này là do các hệ số phải thỏa mãn phương trình ma trận $$ \left[\begin{array}{ccccc} s_0 & s_1 & s_2 & \cdots & s_{L-1} \ s_1 & s_2 & s_3 & \cdots & s_{L} \ & \vchấm & & \vchấm & \ s_{L-1} & s_{L} & s_{L+1} & \cdots & s_{2L-2} \ \end{mảng} \right] \trái[ \begin{array}{c} c_L \ c_{L-1} \ \vdots \ c_1\end{array} \right] = \trái[ \begin{array}{c} s_L \ s_{L+1} \ \vdots \ s_{2L-1}\end{array} \right] $$

ở đâu $c_1,\ldots,c_L$ là các hệ số của phương trình đặc trưng, ​​để có giá trị.

Điều này là do tính chất lặp lại của sự lặp lại, nó phải tiếp tục giữ cho đến biểu tượng cuối cùng ($s_L$) dựa vào đó nó được tính toán không còn là một phần của phương trình ma trận.

Tôi đang sử dụng mã python của bma.bozhu.me (trang web không hoạt động gần đây (sự cố HTTP), chờ câu trả lời rất lâu..)

1. Ví dụ: Chuỗi lặp $s=(0, 1, 0, 1, 1, 1, 0)$

    thứ tự = (0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0)
    (poly, span) = Berlekamp_Massey_algorithm(seq)
   

   đầu ra

   Chuỗi đầu vào là (0, 1, 0, 1, 1, 1, 0). Đa thức đặc trưng của nó là (x^3 + x^1 + 1) và khoảng tuyến tính là 3.

2. Ví dụ: Chuỗi lặp $s=(0, 1, 1, 1, 0, 1)$

   thứ tự = (0,1,1,1,0,1)
   (poly, span) = Berlekamp_Massey_algorithm(seq)
   

   Chuỗi đầu vào là (0, 1, 1, 1, 0, 1). Đa thức đặc trưng của nó là (x^3 + x^2 + 1) và khoảng tuyến tính là 3.

3. Ví dụ: Chuỗi lặp $s=(0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1)$

   thứ tự = (0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1)
   (poly, span) = Berlekamp_Massey_algorithm(seq)
   

   Chuỗi đầu vào là (0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1). Đa thức đặc trưng của nó là (x^5 + x^4 + x^3 + x^2 + x^1 + 1) và khoảng tuyến tính là 5.

Đúng, nó có vẻ có vấn đề, tuy nhiên, không!

Khi Belekamp-Massey tạo ra kết quả, BM tạo đa thức tối giản. Cái này không có nghĩa là nó sẽ khớp với đầu vào tiếp theo của bạn.

Nhớ, một LFSR có độ dài $L$ có thể tạo ra một chuỗi định kỳ có độ dài $2^L-1$; tất cả các $L$-độ dài chuỗi nhị phân ngoại trừ tất cả bằng không. Vì vậy, có bằng cấp $3$ có nghĩa là, một LFSR tối đa có thể tạo ra một chuỗi kích thước $7$. Trình tự định kỳ thực tế là $(0, 1, 1, 1, 0, 1,0)$ lưu ý rằng chúng ta có tất cả các bộ ba trừ số không.

Có thể có một LFSR với các đa thức không nguyên thủy có thể tạo ra các chuỗi của bạn; đây không phải là công việc của BM.

Trường hợp thứ ba có một vấn đề tương tự, dành cho người đọc.

Nhìn vào hồ sơ độ phức tạp tuyến tính

Nhìn vào chất lượng của tính ngẫu nhiên của một chuỗi, Hồ sơ độ phức tạp tuyến tính cũng được đề xuất. Trong trường hợp này, một trình tự được đưa ra và cấu hình của độ phức tạp tuyến tính được tạo ra. Rainer A. Rueppel^* phân tích rộng rãi điều này trong Phân tích và thiết kế mật mã dòng

Trình tự PN được tạo bởi LFSR, như chúng ta có thể thấy, LCP không phát triển! (trình tự của bạn có LCP 3 và 5). Tung đồng xu là chìa khóa để hiểu;

• khi một đầu vào mới được cung cấp cho BM, nếu giai đoạn hiện tại có thể tạo ra nó, thì độ phức tạp tuyến tính sẽ giữ nguyên, nếu không thì độ phức tạp tuyến tính được điều chỉnh để LFST được tạo ra cũng thừa nhận cái trước đó và cái mới.

Cho nên, BM chỉ tạo ra LFSR ngắn nhất cho phần đã cho, nó không giải quyết rằng đầu vào tiếp theo sẽ toán học với LFSR hiện tại.

Lưu ý: Có vẻ như SageMath đang hoạt động.

^* Rainer A. Rueppel là sinh viên của James L. Massey. Có vẻ như đây là cuốn sách đầu tiên trong sê-ri Springer dành cho Mật mã học.

Cho một trình tự $S$ chiều dài $2N$ thuật toán Berlekamp-Massey tìm thấy một LFSR tạo ra cùng một chuỗi $S$ (đặc biệt nó là cái ngắn nhất). Nhưng, bạn không biết nếu chuỗi có khoảng thời gian $N$. Bạn chỉ biết rằng với trạng thái ban đầu chính xác, trình tự được tạo ra sẽ bằng với trình tự trong đầu vào. Tất cả các tính toán sẽ được trong $GF(2)$.

Ví dụ 2: LFSR với đa thức tối thiểu $x^3+x^2+1$ Là $s_{n+3}=s_{n+2}+s_n$ và chúng tôi cần 3 giá trị ban đầu để tạo ra một chuỗi (vì nó phụ thuộc vào $s_n$ và $s_{n+2}$). Trong ví dụ, trạng thái ban đầu là $S=011$, đó là $s_0=0$, $s_1=1$, $s_2=1$. Bạn có thể thấy rằng các giá trị tiếp theo giống như trong chuỗi $s_3=s_2+s_0=1$, $s_4=0$, $s_5=1$. Dù sao thì khoảng thời gian của chuỗi này không phải là 6 và vì vậy LFSR này không phù hợp với chuỗi $S || S$ (nghĩa là nếu bạn tiếp tục tạo ra các bit với LFSR này, bạn sẽ thu được một chuỗi khác với $S||S$).

Ví dụ 3: các bit ban đầu của chuỗi này giống nhau, nhưng lần này chuỗi ngắn nhất phức tạp hơn $s_{n+5}=s_{n+4}+s_{n+3}+s_{n+2}+s_{n+1}+s_{n}$ và nhà nước là $5$ bit dài. Chắc chắn nếu bạn sử dụng trình tự này với trạng thái ban đầu $01110$ bit thứ sáu bằng với chuỗi trong ví dụ 2 (đó là bit $0+1+1+1+0=1$) nhưng với trạng thái ban đầu $01110$ bạn có thể tạo trình tự $011101011101$.