5.4. Алгоритм Берлекемпа-Месси

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

Любая периодическая последовательность может рассматриваться как линейная рекуррентная последовательность. Поэтому для любой периодической последовательности существует некоторый линейный регистр сдвига, который ее вырабатывает. Если элементы, образующие период последовательности, выбираются случайно, то степень минимального многочлена такой последовательности близка к величине ее периода. Поэтому линейная сложность может рассматриваться как характеристика сложности аналитического строения псевдослучайной последовательности. Низкую линейную сложность имеют слабые в криптографическом отношении последовательности. Вместе с тем высокая линейная сложность не гарантирует отсутствия других недостатков. Например, для генерации последовательности, период которой имеет вид (0,0,…,0,1), требуется линейный регистр, длина которого совпадает с длиной периода этой последовательности, однако ясно, что считать эту последовательность случайной нельзя.

Эффективным методом нахождения линейного регистра сдвига минимальной длины, генерирующего заданную последовательность, является алгоритм Берлекемпа-Месси.

Пусть Р – некоторое поле, е – единица поля Р. Обозначим через и=(u(0),...,u(l – 1)) начальный отрезок произвольной последовательности и элементов поля Р. Будем говорить, что многочлен

вырабатывает отрезок и, если

то-есть если данный отрезок последовательности является отрезком некоторой линейной рекуррентной последовательности с характеристическим многочленом G(x).

Алгоритм Берлекемпа-Месси строит многочлен G(x) наименьшей степени, вырабатывающий отрезок и. Приведем одну из многочисленных модификаций алгоритма со сложностью, оцениваемой величиной 6т²(1+о(1)) операций поля Р.

Определим операцию умножения последовательности на многочлен.

Для произвольного многочлена

и последовательности v положим H(x)v=w, где

Будем говорить, что многочлен G(x) степени т вырабатывает l  т знаков последовательности и, если выполняется равенство

то есть если первые l — т знаков последовательности v равны нулю, а следующий за ними отличен от нуля.

Для многочлена G(x)P[x] степени т и последовательности и введем параметры l_и(G) и k_и(G) = l_и(G) – т, где l_и(G) – число знаков последовательности и, вырабатываемых многочленом G(x). Ясно, что k_и(G) – максимальное число первых подряд идущих нулей в последовательности G(x)u (либо ).

Будем индуктивно строить последовательность многочленов G₀(x), G₁(x),... неубывающих степеней 0= т₀ < т₁  т₂ ... .

Начальные условия: G₀(x)=e, т₀ =0.

Этап 1. Если

то полагаем

Если G₁(x)и = 0, то есть если k_и(G₁) = , то G₁(x) – искомый минимальный многочлен ЛРП и. В противном случае строим G₂(x).

Этап t+1. Пусть многочлены G₀(x),...,G_t(x) уже построены, и степень degG_j(x) многочлена G_j(x) равна т_j, причем 0= т₀ < т₁  … т_t. Пусть выполняются соотношения

Определим число s = s(t) так, чтобы выполнялись условия т_t = т_t-1 = …= т_s+1 > т_s (такое s найдется, так т₁ > т₀). Положим

если k_t  k_s,

если k_t > k_s.

Если G_t+1(x)u = 0, то нужный многочлен построен. В противном случае строим G_t+2(x) .

Теорема 2. Если и – линейная рекуррентная последовательность над полем Р с минимальным многочленом F(x) степени т, то F(x)= G_r(x) для некоторого подходящего значения r  2т–1–k₀.