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?

Я использую код Python bma.bozhu.me (сайт в последнее время не работает (проблема с HTTP), долго жду ответов..)

1. Пример: повторяющаяся последовательность $s=(0, 1, 0, 1, 1, 1, 0)$

    последовательность = (0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0)
    (poly, span) = Berlekamp_Massey_algorithm(seq)
   

   выходы

   Входная последовательность (0, 1, 0, 1, 1, 1, 0). Его характеристический полином равен (x^3 + x^1 + 1), а линейный диапазон равен 3.

2. Пример: повторяющаяся последовательность $s=(0, 1, 1, 1, 0, 1)$

   последовательность = (0,1,1,1,0,1)
   (poly, span) = Berlekamp_Massey_algorithm(seq)
   

   Входная последовательность (0, 1, 1, 1, 0, 1). Его характеристический полином равен (x^3 + x^2 + 1), а линейный диапазон равен 3.

3. Пример: повторяющаяся последовательность $s=(0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1)$

   последовательность = (0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1)
   (poly, span) = Berlekamp_Massey_algorithm(seq)
   

   Входная последовательность (0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1). Его характеристический полином равен (x ^ 5 + x ^ 4 + x ^ 3 + x ^ 2 + x ^ 1 + 1), а линейный диапазон равен 5.

Да, кажется проблематичным, однако, не!

Когда Белекамп-Месси дал результат, BM производит минимальный многочлен. Этот не означает, что он будет соответствовать вашему следующему вводу.

Помните, LFSR длины $L$ может генерировать периодическую последовательность длины $2^L-1$; все $L$двоичные строки -length, за исключением всех нулей. Так, имея степень $3$ означает, что максимальный LFSR может генерировать последовательность размера $7$. Фактическая периодическая последовательность $(0, 1, 1, 1, 0, 1,0)$ обратите внимание, что у нас есть все тройки, кроме нуля.

Может быть LFSR с непримитивными полиномами, которые могут создавать ваши последовательности; это не работа БМ.

В третьем случае аналогичная проблема, оставляемая читателю.

Глядя на профиль линейной сложности

Рассматривая качество случайности последовательности, также предлагается профиль линейной сложности. В этом случае задается последовательность и создается профиль линейной сложности. Райнер А. Рюппель^* тщательно проанализировал это в Анализ и проектирование потоковых шифров

PN-последовательность генерируется LFSR, как видим, LCP не растет! (ваши последовательности имеют LCP 3 и 5). Подбрасывание монеты является ключом к пониманию;

• когда в BM подается новый вход, если текущая стадия может его произвести, линейная сложность остается прежней, если нет, то линейная сложность корректируется так, чтобы созданный LFST допускал и предыдущий, и новый.

Так, BM производит только кратчайший LFSR для данной части, он не указывает, что следующий вход будет математическим с текущим LFSR.

Примечание. Кажется, SageMath работает.

^* Райнер А. Рюппель был студентом Джеймс Л. Мэсси. Кажется, это первая книга из серии Springer, посвященной криптографии.

Один из аспектов этого заключается в том, что если вычисленная до сих пор повторяемость последовательности $(s_t)_{t \geq 0}$ длина $L$, вам нужно дождаться наблюдения $2L$ символы, чтобы убедиться, что сгенерированный до сих пор LFSR действительно действителен. Это связано с тем, что коэффициенты должны удовлетворять матричному уравнению $$ \left[\begin{массив}{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{массив} \right] \оставил[ \начать{массив}{с} c_L \ c_{L-1} \ \vdots \ c_1\end{массив} \right] знак равно \оставил[ \начать{массив}{с} s_L \ s_{L+1} \ \vdots \ s_{2L-1}\end{массив} \right] $$

куда $c_1,\ldots,c_L$ являются коэффициентами характеристического уравнения, чтобы быть действительными.

Это связано с перекрывающимся характером повторения, оно должно продолжаться до последнего символа ($s_L$), на основе которого он был рассчитан, больше не является частью матричного уравнения.

Учитывая последовательность $S$ длины $2N$ алгоритм Берлекэмпа-Месси находит LFSR, который дает ту же последовательность $S$ (в частности, это самый короткий). Но вы не знаете, есть ли в последовательности период $N$. Вы только знаете, что при правильном начальном состоянии полученная последовательность будет равна той, что была введена. Все расчеты будут в $GF(2)$.

Пример 2: LFSR с минимальным полиномом $х^3+х^2+1$ является $s_{n+3}=s_{n+2}+s_n$ и нам нужно 3 начальных значения для создания последовательности (потому что это зависит от $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 не подходит для этой последовательности. $С || С$ (то есть, если вы продолжите производить биты с помощью этого 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$.