Алгоритм Берлекампа — данный алгоритм предназначен для факторизации полиномов, позволяет разлагать полиномы на неприводимые сомножители. Алгоритм был разработан Элвином Берлекэмпом в 1967 году. Следует различать алгоритм Берлекэмпа и алгоритм Берлекэмпа — Мэсси, предназначенный для нахождения реккурентных зависимостей в последовательностях.

Описание алгоритма

Алгоритм состоит в основном из матрицы сокращения и вычисления многочлена НОД. В качестве входных параметров в алгоритме Берлекэмпа используются полином степени над полем F, без повторяющихся множителей. На выходе получаем неприводимые множители на которые разлагается полином . Все возможные множители полинома составляют кольцо:

Алгоритм вычисляет полиномы удовлетворяющие условию

.

Эти полиномы образуют алгебру R, также называемую алгеброй Берлекэмпа, которую можно рассматривать как n-мерное векторное пространство над ). Полиномы удовлетворяют условию:

В общем случае не каждый НОД (gcd) в данной формуле будет нетривиальным множителем для Алгоритм Берлекэмпа позволяет находить мономы , тем самым вычисляя базисные множители алгебры Берлекэмпа (R). Это возможно при рассмотрении алгебры Берлекэмпа как матрицы размером из что есть матрица полиномов, называемая . Если то  — коэффициенты при -й степени в выражении mod . То есть

Положим: мы можем сопоставить вектор : Нетрудно заметить, что вектор соответствует mod . тогда и только тогда, когда (где матрица размера ) Вычислив матрицу потом построим искомые полиномы

Литература

• Berlekamp, Elwyn R. (1967). «Factoring Polynomials Over Finite Fields». Bell Systems Technical Journal 46: 1853–1859. Later republished in: Berlekamp Elwyn R. Algebraic Coding Theory. — McGraw Hill, 1968.

Примечания