- Алгоритм Берлекампа
-
Алгоритм Берлекампа — данный алгоритм предназначен для факторизации полиномов, позволяет разлагать полиномы на неприводимые сомножители. Алгоритм был разработан Элвином Берлекэмпом в 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.
Примечания
Категории:- Вычислительная алгебра
- Алгоритмы
Wikimedia Foundation. 2010.