Алгоритм Берлекампа

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

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

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

$R = \frac{\mathbb{F}_q[x]}{\langle f(x) \rangle}.$

Алгоритм вычисляет полиномы $g(x) \in R$ удовлетворяющие условию

$g(x)^q \equiv g(x) \pmod{f(x)}$.

Эти полиномы образуют алгебру R, также называемую алгеброй Берлекэмпа, которую можно рассматривать как n-мерное векторное пространство над $\mathbb{F}_q$). Полиномы $g(x)$ удовлетворяют условию:

$f(x) = \prod_{s \in \mathbb{F}_q} \gcd(f(x),g(x)-s).$

В общем случае не каждый НОД (gcd) в данной формуле будет нетривиальным множителем для $f(x)$ Алгоритм Берлекэмпа позволяет находить мономы $g(x)$, тем самым вычисляя базисные множители алгебры Берлекэмпа (R). Это возможно при рассмотрении алгебры Берлекэмпа как матрицы размером $n \times n$ из $\mathbb{F}_q$ что есть матрица полиномов, называемая $\mathcal{Q}$. Если $\mathcal{Q}=[q_{i,j}]$ то $q_{i,j}$ — коэффициенты при $j$ -й степени в выражении $x^{iq}$ mod $f(x)$. То есть

$x^{iq} \equiv q_{i,n}x^n + q_{i,n-1}x^{n-1} + \ldots + q_{i,0} \pmod{f(x)}$

$g(x) \in R$ Положим:$g(x) = g_nx^n+g_{n-1}x^{n-1} + \ldots + g_0,$ мы можем сопоставить вектор :$g = (g_0, g_1, \ldots, g_n).$ Нетрудно заметить, что вектор $g\mathcal{Q}$ соответствует $g(x)^q$ mod $f(x)$. $g(x) \in R$ тогда и только тогда, когда $g(\mathcal{Q}-I)=0$ (где $I$ матрица размера $n \times n$) Вычислив матрицу $\mathcal{Q}-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.

Примечания