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

Шаблон:Не путать Алгоритм Берлекэмпа — алгоритм, предназначенный для факторизации унитарных многочленов над конечным полем. Разработан Элвином Берлекэмпом в 1967 году. Может использоваться также для проверки неприводимости многочленов над конечными полями.Шаблон:Переход Основная идея алгоритма заключается в возможности представления исходного многочлена в виде произведения наибольших общих делителей самого многочлена и некоторых многочленов, которые с точностью до свободного члена являются $f$-разлагающими.

Алгоритм Берлекэмпа имеет большую вычислительную сложность, поэтому был разработан ряд дополнительных методов, позволяющих сократить количество необходимых математических операций. Однако, несмотря на свою сложность, алгоритм Берлекэмпа был реализован в системах компьютерной алгебры. Алгоритм нашёл широкое применение в теории кодирования и в изучении линейных рекуррентных соотношений в конечных полях. Имеется много вычислительных задач в алгебре и в теории чисел, которые так или иначе связаны с разложением многочленов над конечными полями, например, разложение на множители многочленов над кольцом целых чисел, отыскание разложения простого рационального числа в поле алгебраических чисел, вычисление группы Галуа некоторого уравнения над полем рациональных чисел и построение расширений полей.

История создания

Американский математик, профессор Калифорнийского университета Берлекэмп занимался изучением циклических кодов обнаружения и исправления ошибок, в том числе кода Боуза — Чоудхури — Хоквингема, свойства которых зависят от делителей порождающих многочленов. Технические достижения Берлекэмпа в области декодирования этих кодов сделали их более привлекательными с практической точки зренияШаблон:Sfn.

Алгоритм был впервые изложен в статье «Factoring Polynomials Over Finite Fields»Шаблон:Sfn и позже воспроизведён в книге «Algebraic Coding Theory»Шаблон:Sfn. В этой работе 1967 года Шаблон:Sfn Берлекэмп пишет, что проблема факторизации возникает в трудах Голомба. Однако, возможность использования матрицы $B$ для определения числа нормированных сомножителей многочлена $f(x)$ была впервые замечена в статье Шаблон:Нп3. В статье Батлера было установлено, что ранг матрицы $B-E$ равен $n-k$, другое доказательство этого факта было дано Шварцем.

Алгоритм Берлекэмпа упоминался во множестве работШаблон:Sfn и являлся основным алгоритмом решения проблемы факторизации до появления в 1981 году Шаблон:Нп3. Была разработана техника позволяющая разложить многочлен на множители за $O(n^{(\omega +1)/2+o(1)}+n^{1+o(1)}\log q),$ где $\omega$ — показатель в оценке сложности перемножения квадратных матрицШаблон:Sfn.

Постановка и определения

Рассматривается задача факторизации многочлена $f(x)$ степени $n$ ($n\ge 2$) над конечным полем ${𝔽}_q$ ($q=p^m$, $p$ — простое число)Шаблон:Sfn на различные неприводимые унитарные многочлены $f(x)=f_1(x{)}^{e_1}\cdots f_k(x{)}^{e_k}$.

Для использования в алгоритме строится матрица $B=(b_{ij}{)}_{i=0,j=0}^{n-1,n-1}$ согласно следующим условиям:

$x^{iq}\equiv \sum _{j=0}^{n-1}{b}_{ij}{x}^j(\mathrm{mod}f(x))i=\overline{0,n-1}$.

Многочлен $h(x)\in {𝔽}_q[x]$ такой, что $1⩽\mathrm{deg}h(x)<n,{h(x)}^q\equiv h(x)(\mathrm{mod}f(x))$, называется $f$-разлагающим многочленомШаблон:Sfn.

Основной случай

Блок-схема для алгоритма Берлекэмпа — основной случай

Алгоритм факторизации над конечным полем ${𝔽}_q$ многочлена вида:

$f(x)=f_1(x)\cdots f_k(x)$

состоит из следующих шагов:

1. Вычисление матрицы $B$Шаблон:Sfn.
2. Поиск базиса $\overline{e_1},\dots ,\overline{e_k}$ подпространства решений системы линейных уравненийШаблон:Sfn:

   $(B-E_n{)}^T𝐱=\mathrm{𝟎}$,

   при этом удаётся выбрать вектор $\overline{e_1}=(1,0,\mathrm{....},0)$, так как он всегда будет присутствоватьШаблон:Sfn в базисе пространства решений ввиду того, что $x^{iq}\equiv 1(\mathrm{mod}f(x))$ при $i=0$.

3. Найденное число $k$ есть число неприводимых делителейШаблон:Sfn $f(x)$.
   • Шаблон:ЯкорьЕсли $k=1$, то многочлен является неприводимым.
   • Если $k>1$, то векторы $\overline{e_l}$ имеют вид $(h_{l,0},\dots ,h_{l,n-1})$. По этим числам строятся $f$-разлагающие многочлены:

     $h_l(x)=\sum _{i=0}^{n-1}{h}_{l,i}{x}^i,l=\overline{2,k},h_1(x)=1.$.

4. Поиск разложенияШаблон:Sfn:

   $f(x)=\prod _{c\in {𝔽}_q,}gcd(f(x),h_2(x)-c)$

   в виде:

   $f(x)=\prod _m{g}_{m,2}(x)$,

   где $g_{m,s}(x),s=\overline{2,k}$ в общем случае не являются неприводимыми. Функции $g_{m,s}(x)$ факторизуются таким же способомШаблон:Sfn, то есть:

   $g_{m,s}(x)=\prod _{c\in {𝔽}_q,}gcd(g_{m,s}(x),h_{s+1}(x)-c),s=\overline{2,k-1}$.

Общий случай

Блок-схема для алгоритма Берлекэмпа — сведение к основному случаю

Задача факторизации произвольного унитарного многочлена сводится к рассмотрению основного случая. Для этого вычисляется многочлен

$d(x)=gcd(f(x),f^{\text{'}}(x))$

с применением алгоритма Евклида.

• Если $d(x)=1,$ то многочлен не содержит кратных корней, так как кратный корень одновременно является и корнем производнойШаблон:Sfn.
• Если $d(x)=f(x),$ то $f^{\text{'}}(x)=0,$ и значит $f(x)=g(x{)}^p,g(x)\in {𝔽}_q[x].$ Если $g^{\text{'}}(x)=0,$ то для $g(x)$ необходимо проделать описанную процедуру до тех пор пока не будет получено разложение $f(x)=h(x{)}^{p^s},h\text{'}(x)\ne 0.$ Многочлен $h(x)$ удовлетворяет требованиям основного случаяШаблон:Sfn.
• Иначе, многочлен $d(x)$ является нетривиальным делителем многочлена $f(x)$. В свою очередь, многочлен $\frac{f(x)}{d(x)}$ не имеет кратных неприводимых сомножителейШаблон:Sfn. Если $d(x)$ содержит кратные сомножители, то к нему также применяется описанная процедура. Зная эти разложения, легко получить разложение $f(x)$.

Таким образом, задача разложения произвольного унитарного многочлена над конечным полем ${𝔽}_q[x]$ сводится к разложению на множители конечного числа многочленов, которые не имеют кратных неприводимых сомножителей, то есть к основному случаюШаблон:Sfn.

Обоснование

Пусть:

$f(x)=f_1(x{)}^{e_1}\cdots f_k(x{)}^{e_k}$, где $e_i=1,i=\overline{1,k}$.

Согласно китайской теореме об остатках существует единственный многочлен для любого набора $(c_1,\mathrm{...},c_k)$ элементов поля ${𝔽}_q$Шаблон:Sfn:

$h(x)\in {𝔽}_q[x],$

такой что:

$h(x)\equiv c_i(\mathrm{mod}{f}_i(x)),i=\overline{1,k},\mathrm{deg}h(x)<\mathrm{deg}f(x)$.

Многочлен $h(x)$ удовлетворяет условиюШаблон:Sfn:

$h(x)\equiv c_i\equiv c_i^q\equiv h(x{)}^q(\mathrm{mod}{f}_i(x)),i=\overline{1,k}$,

и поэтомуШаблон:Sfn:

$h(x{)}^q\equiv h(x)(\mathrm{mod}f(x)),\mathrm{deg}h(x)<degf(x)$.

Из условия:

$h(x{)}^q-h(x)=\prod _{c\in {𝔽}_q}(h(x)-c)\equiv 0(\mathrm{mod}f(x))$,

и из взаимной простоты сомножителей в правой части следует, что каждый неприводимый делитель многочлена $f(x)$ делит один, и только один из многочленов $h(x)-c$. Таким образом, доказана справедливость и единственность разложенияШаблон:Sfn:

$f(x)=\prod _{c\in {𝔽}_q}gcd(f(x),h(x)-c).$

Для нахождения многочлена:

$h(x)=a_0+a_1{x}^1+\dots +a_{n-1}{x}^{n-1}\in {𝔽}_q$

рассмотрим сравнение:

$h(x{)}^q\equiv h(x)(\mathrm{mod}f(x))$,

которое равносильно условиюШаблон:Sfn:

$\sum _{i=0}^{n-1}{a}_i{x}^{iq}\equiv \sum _{i=0}^{n-1}{a}_i{x}^i(\mathrm{mod}f(x))$.

По определению матрицы $B$ получим:

$\sum _{i=0}^{n-1}{a}_i\sum _{j=0}^{n-1}{b}_{ij}{x}^j=\sum _{i=0}^{n-1}{a}_i{x}^i$,

поэтомуШаблон:Sfn:

$\sum _{i=0}^{n-1}{a}_i{b}_{ij}=a_j,j=\overline{0,n-1}$.

Полученная система уравнений определяет коэффициенты $f$-разлагающих многочленов и может быть записана в виде:

$(a_0,a_1,\mathrm{...},a_{n-1})B=(a_0,a_1,\mathrm{...},a_{n-1})$

или:

$(a_0,a_1,\mathrm{...},a_{n-1})(B-E_n)=\mathrm{𝟎}$Шаблон:Sfn.

Сложность алгоритма

Сложность алгоритма составляет $O(n^3+qkn)$ математических операцийШаблон:Sfn. Алгоритм будет эффективен только для небольших полей. Это связано с необходимостью перебора всех $c\in {𝔽}_q$.

Усовершенствования

• В случае простого поля, если значение $p$ велико, то перебор значений $c\in \mathbb{Z}/p\mathbb{Z}$ займёт много времени. Однако, возможно определить множество $M$, состоящее из $c$, для которых $gcd(f(x),h(x)-c)$ нетривиаленШаблон:Sfn. Для этого необходимо найти корни результантаШаблон:Sfn $R(c)$, которые и будут составлять множество $M$.
• Ещё один метод разложения унитарного многочлена $f(x)\in GF(q)[x]$, не имеющего кратных неприводимых множителей, основан на приведении некоторой эффективно вычислимой с помощью алгоритма Берлекэмпа матрицы A к диагональному видуШаблон:Sfn. Однако сам процесс диагонализации довольно сложен.
• В работе Калтофена и Лобо была предложена вероятностная версия алгоритма Берлекэмпа, позволяющая разложить на множители многочлен $f(x)\in GF(q)[x]$ степени $n$ за $O((n\log n+\log q)\cdot n(\log n)\log (\log n))$ арифметических операций. Алгоритм Калтофена — Лобо был реализован на компьютере, и оказался эффективным для многочленов высокой степени, например, для многочленов степени 10001 над полем $\mathbb{Z}/127\mathbb{Z}$ он работает около 102,5 часов на компьютере Sun-4.

Применение

Алгоритмы факторизации многочленов важны для теории кодирования и для изучения линейных рекуррентных соотношений в конечных полях. Также алгоритм Берлекэмпа используется для вычисления группы Галуа уравнения над полем рациональных чисел и построения решений полей, разложения многочленов над кольцом целых чисел, для отыскания разложения простого рационального числа в поле алгебраических чисел, и для некоторых других вычислительных задачШаблон:Sfn. Алгоритм исчисления порядка использует алгоритмы факторизации многочленов для решения задачи отыскания дискретного логарифмаШаблон:Sfn, на вычислительной сложности которой построена схема Эль-Гамаля.

Реализации в системах компьютерной алгебры

В системе компьютерной алгебры Шаблон:Iw алгоритм Берлекэмпа может быть использован посредством команды factormod.

Литература

• Шаблон:Статья BSTJ Later republished in: Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга Шаблон:Wayback