|
Алгоритм БерлекампаАлгоритм Берлекампа, данный алгоритм предназначен для факторизации полиномов, позволяет разлагать полиномы на неприводимые сомножители. Алгоритм был разработан Элвином Берлекэмпом в 1967 году. Следует различать алгоритм Берлекэмпа и алгоритм Берлекэмпа — Мэсси, предназначенный для нахождения реккурентных зависимостей в последовательностях. Алгоритм состоит в основном из матрицы сокращения и вычисления многочлена НОД. В качестве входных параметров в алгоритме Берлекэмпа используются полином f(x) степени n над полем F, без повторяющихся множителей. На выходе получаем неприводимые множители на которые разлагается полином f(x). Все возможные множители полинома f(x) составляют кольцо:
Алгоритм вычисляет полиномы удовлетворяющие условию . Эти полиномы образуют алгебру R, также называемую алгеброй Берлекэмпа, которую можно рассматривать как n-мерное векторное пространство ). Полиномы g(x) удовлетворяют условию:
В общем случае не каждый НОД (gcd) в данной формуле будет нетривиальным множителем для f(x) Алгоритм Берлекэмпа позволяет находить мономы g(x), тем самым вычисляя базисные множители алгебры Берлекэмпа (R). Это возможно при рассмотрении алгебры Берлекэмпа как матрицы размером из что есть матрица полиномов, называемая . Если то qi,j — коэффициенты при j -й степени в выражении xiq mod f(x). То есть
Положим: мы можем сопоставить вектор : Нетрудно заметить, что вектор соответствует g(x)q modf(x). тогда и только тогда, когда (где I матрица размера ) Вычислив матрицу потом построим искомые полиномы g(x) Лит.: 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. |
Loading
|