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

Пусть P – некоторое поле, e – единица поля P. Обозначим через начальный отрезок произвольной последовательности u элементов поля P. Будем говорить, что многочлен

 

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

,

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

Определим функцию умножения последовательности на многочлен. Для произвольного многочлена и последовательности v положим H(x) · v = w, где

 

Многочлен G(x) вырабатывает l ³ m знаков последовательности u, если выполняется равенство

 

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

Для многочлена G(x) Î P[x] степени m и последовательности u введем параметры lu(G) и ku(G) = lu(G) – m Î N È {0, +¥}, где lu(G) – число знаков последовательности u, вырабатываемых многочленом G(x). Ясно, что ku(G) – максимальное число первых подряд идущих нулей в последовательности G(x) · u (либо ¥).

Будем индуктивно строить последовательность многочленов G0(x), G1(x), … неубывающих степеней 0 = m0 < m1 £ m2 £ … .

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

Этап 1. Если

 

то полагаем

 

Если G1(xu = 0, то есть если ku(G1) = ¥, то G1(x) – искомый минимальный многочлен ЛРП u. В противном случае строим G2(x).

Этап t + 1. пусть многочлены G0(x), …, Gt(x) уже построены, и степень многочлена Gj(x) равна mj, причем 0 = m0 < m1 £ m2 £ … mt. Пусть выполняются соотношения

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

 

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

Теорема: Если u – линейная рекуррентная последовательность над полем P с минимальным многочленом степени m, то F(x) = Gt(x) для некоторого подходящего значения t £ 2m – 1 – k0.