Главная

Пример применения алгоритма Берлекэмпа-Месси

2025-06-22 в 13:26, admin, рубрики: алгоритм берлекэпма-месси, ЛРП, характеристические многочлены

Алгоритм Берлекэмпа-Месси используется для поиска минимального многочлена ЛРП. Его внешний вид может быть слегка пугающим, особенно если без должной подготовки нарваться на доказательства его корректности. Мы же здесь просто посмотрим работу данного алгоритма на конкретном примере и произведём проверку с помощью средств линейной алгебры.

Н.Н. Токарева "Симметричная криптография"

Пусть у нас есть следующий отрезок последовательности 101011110, найдём его минимальный многочлен, следуя алгоритму выше.

Предварительные сведения

Перейдём к реализации алгоритма

$text{Этап 0: }G_0(x)=1; m_0=0; k_0=0 \ G_0cdot(101011110)=101011110\ text{Понятно, что $G_0$ не вырабатывает данный нам отрезок}$ $text{Этап 1: } G_1=x + 0=x; m_1=1; k_1=1 \ G_1 cdot (101011110)=01011110 \ text{$G_1$ тоже не подходит, так как с начальным состоянием 1 вырабатывает}\ text{последовательность 100000000, что отлично от нашей уже на третьем шаге}$ $text{Этап 2: } s=0, text{ } t=1 Rightarrow G_2=xcdot x + 1=x^2 + 1; m_2=2; k_2=3 \ G_2 cdot (101011110)=0001001 \ text{$G_2$ с начальными значениями 10 вырабатывает последовательность 101010101}$ $text{Этап 3: } s=1, text{ } t=2 Rightarrow G_3=x^2(x^2 + 1) + x=x^4 + x^2 + x; m_3=4; k_3=3 \ G_3 cdot (101011110)=00010 \ text{$G_3$ по начальным данным 1010 даёт 101001110 - уже тепло}$ $text{Этап 4: } s=2, text{ } t=3 Rightarrow G_4=x^4 + x^2 + x + x^2 + 1=x^4 + x + 1; m_4=4; k_4=4 \ G_4 cdot (101011110)=00000 \ text{$G_4$ даёт 101011110 - Бинго! Минимальный многочлен найден}$

Проверка

Мне случилось решать задачу поиска минимального многочлена без знания данного алгоритма, на помощь приходит более интуитивный метод неопределённых коэффициентов.

Пользоваться будем известным свойством ЛРП о том, что если какое-то состояние ЛРП, то следующее можно найти в виде $S_{i+1}=S_i cdot A$ , где - сопровождающая матрица ЛРП.

Отбросим многочлены степени 0 и 1 как очевидно неподходящие и предположим, что у искомого характеристического многочлена степень 2, то есть он имеет вид , то есть

$(10)begin{pmatrix}0 text{ } a_0 \ 1 text{ } a_1end{pmatrix}=(01) Rightarrow (0, a_0)=(0, 1) Rightarrow a_0=1 \ (01)begin{pmatrix}0 text{ } 1 \ 1 text{ } a_1end{pmatrix}=(10) Rightarrow (1, a_1)=(1, 0) Rightarrow a_1=0 \ text{Но мы уже видели, что многочлен $x^2 + 1$ нам не подходит}$

Двигаемся дальше и рассмотрим многочлен

$(101)begin{pmatrix}0 text{ } 0 text{ } a_0 \ 1 text{ } 0 text{ } a_1 \ 0 text{ } 1 text{ } a_2end{pmatrix}=(010) Rightarrow (0, 1, a_0 + a_2)=(0, 1, 0) Rightarrow a_0 + a_2=0 \ (010)begin{pmatrix}0 text{ } 0 text{ } a_0 \ 1 text{ } 0 text{ } a_1 \ 0 text{ } 1 text{ } a_2 end{pmatrix}=(101) Rightarrow (1, 0, a_1)=(1, 0, 1) Rightarrow a_1=1 \ (101)begin{pmatrix} 0 text{ } 0 text{ } a_0 \ 1 text{ } 0 text{ } a_1 \ 0 text{ } 1 text{ } a_2 end{pmatrix}=(011) Rightarrow (0,1, a_0 + a_2)=(011) Rightarrow a_0 + a_2=1 text{ } ?!$

Рассмотрим многочлен четвёртой степени

$(1010) begin{pmatrix} 0 text{ } 0 text{ } 0 text{ } a_0 \ 1 text{ } 0 text{ } 0 text{ } a_1 \ 0 text{ } 1 text{ } 0 text{ } a_2 \ 0 text{ } 0 text{ } 1 text{ } a_3 end{pmatrix}=(0101) Rightarrow (0,1,0,a_0 + a_2)=(0,1,0,1) Rightarrow a_0+a_2=1$ $(0101) begin{pmatrix} 0 text{ } 0 text{ } 0 text{ } a_0 \ 1 text{ } 0 text{ } 0 text{ } a_1 \ 0 text{ } 1 text{ } 0 text{ } a_2 \ 0 text{ } 0 text{ } 1 text{ } a_3 end{pmatrix}=(1011) Rightarrow (1,0,1,a_1 + a_3)=(1,0,1,1) Rightarrow a_1+a_3=1$ $(1011) begin{pmatrix} 0 text{ } 0 text{ } 0 text{ } a_0 \ 1 text{ } 0 text{ } 0 text{ } a_1 \ 0 text{ } 1 text{ } 0 text{ } a_2 \ 0 text{ } 0 text{ } 1 text{ } a_3 end{pmatrix}=(0111) Rightarrow (0,1,1,a_0 + a_2 + a_3)=(0,1,1,1), \ text{следовательно, } a_0 + a_2+a_3=1 Rightarrow a_3=a_2=0, a_0=a_1=1$

То есть, что совпадает с ранее полученным результатом. Для полной строгости осталось проверить, что он правда генерирует предоставленный нам отрезок ЛРП, но мы это уже делали ранее. А так как подъём осуществлялся снизу вверх, то попутно было показано, что он минимальный.