22.06.2025 13:26
Morgana0_0 2 839 Источник

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

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

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

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

Базовые определения и теоремы
Базовые определения и теоремы

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

\text{Этап 0: }G_0(x) = 1; m_0 = 0; k_0 = 0 \\ G_0\cdot(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 = x\cdot 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 какое-то состояние ЛРП, то следующее можно найти в виде S_{i+1} = S_i \cdot A, где A - сопровождающая матрица ЛРП.

Отбросим многочлены степени 0 и 1 как очевидно неподходящие и предположим, что у искомого характеристического многочлена степень 2, то есть он имеет вид f(x) = x^2 + a_1x + a_0 , то есть

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

Двигаемся дальше и рассмотрим многочлен f(x) = x^3 + a_2x^2 + a_1x + a_0

(101)\begin{pmatrix}0 \text{ } 0 \text{ } a_0 \\ 1 \text{ } 0 \text{ } a_1 \\ 0 \text{ } 1 \text{ } a_2\end{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{ } ?!

Рассмотрим многочлен четвёртой степени f(x) = x^4 + a_3x^3 + a_2x^2 + a_1x + a_0

(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

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


P.s. а ещё у меня есть тгк с другими не менее интересными заметками https://t.me/mathematuchka

Комментарии (2)


  1. wataru
    22.06.2025 14:27
    #28470302

    Стоило бы немного определений и контекста добавить.

    А так, даже на википедии этот алгоритм объяснен лучше.


    1. DoomeR18G
      22.06.2025 14:27
      #28470478

      Факт