Алгоритм Берлекэмпа (Glikjnmb >yjlytzbhg)

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

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

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

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

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

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

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

Рассматривается задача факторизации многочлена $f(x)$ степени $n$ ( $n\geq 2$ ) над конечным полем $\mathbb {F} _{q}$ ( $q=p^{m}$ , $p$ — простое число)^[12] на различные неприводимые унитарные многочлены $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}{\pmod {f(x)}}\quad i={\overline {0,n-1}}

.

Многочлен $h(x)\in \mathbb {F} _{q}[x]$ такой, что $1\leqslant \deg {h(x)}<n,\quad {h(x)}^{q}\equiv h(x){\pmod {f(x)}}$ , называется $f$ -разлагающим многочленом^[13].

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

Алгоритм факторизации над конечным полем $\mathbb {F} _{q}$ многочлена вида:

f(x)=f_{1}(x)\cdots f_{k}(x)

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

Вычисление матрицы $B$ ^[14].
Поиск базиса ${\overline {e_{1}}},\dots ,{\overline {e_{k}}}$ подпространства решений системы линейных уравнений^[15]:
$(B-E_{n})^{T}\mathbf {x} =\mathbf {0}$ ,

при этом удаётся выбрать вектор ${\overline {e_{1}}}=(1,\;0,\;....\;,\;0)$ , так как он всегда будет присутствовать^[15] в базисе пространства решений ввиду того, что $x^{iq}\equiv 1{\pmod {f(x)}}$ при $i=0$ .
Найденное число $k$ $k$ есть число неприводимых делителей^[14] $f(x)$ $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},\quad l={\overline {2,\;k}},\quad h_{1}(x)=1.$ .
Поиск разложения^[15]:
$f(x)=\prod _{c\in \mathbb {F} _{q},}\gcd(f(x),h_{2}(x)-c)$

в виде:
$f(x)=\prod _{m}g_{m,\;2}(x)$ ,

где $g_{m,\;s}(x),\quad s={\overline {2,k}}$ в общем случае не являются неприводимыми. Функции $g_{m,\;s}(x)$ факторизуются таким же способом^[15], то есть:
$g_{m,\;s}(x)=\prod _{c\in \mathbb {F} _{q},}\gcd(g_{m,\;s}(x),h_{s+1}(x)-c),\quad s={\overline {2,k-1}}$ .

Общий случай

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

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

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

Если $d(x)=1,$ то многочлен не содержит кратных корней, так как кратный корень одновременно является и корнем производной^[16].
Если $d(x)=f(x),$ то $f^{'}(x)=0,$ и значит $f(x)=g(x)^{p},\quad g(x)\in \mathbb {F} _{q}[x].$ Если $g^{'}(x)=0,$ то для $g(x)$ необходимо проделать описанную процедуру до тех пор пока не будет получено разложение $f(x)=h(x)^{p^{s}},h{'}(x)\neq 0.$ Многочлен $h(x)$ удовлетворяет требованиям основного случая^[16].
Иначе, многочлен $d(x)$ является нетривиальным делителем многочлена $f(x)$ . В свою очередь, многочлен ${\frac {f(x)}{d(x)}}$ не имеет кратных неприводимых сомножителей^[16]. Если $d(x)$ содержит кратные сомножители, то к нему также применяется описанная процедура. Зная эти разложения, легко получить разложение $f(x)$ .

Таким образом, задача разложения произвольного унитарного многочлена над конечным полем $\mathbb {F} _{q}[x]$ сводится к разложению на множители конечного числа многочленов, которые не имеют кратных неприводимых сомножителей, то есть к основному случаю^[16].

Обоснование

Пусть:

f(x)=f_{1}(x)^{e_{1}}\cdots f_{k}(x)^{e_{k}}

, где

\quad e_{i}=1,\quad i={\overline {1,k}}

.

Согласно китайской теореме об остатках существует единственный многочлен для любого набора $(c_{1},\;...,\;c_{k})$ элементов поля $\mathbb {F} _{q}$ ^[17]:

h(x)\in \mathbb {F} _{q}[x],

такой что:

h(x)\equiv c_{i}{\pmod {f_{i}(x)}},\;i={\overline {1,\;k}},\quad \deg {h(x)}<\deg {f(x)}

.

Многочлен $h(x)$ удовлетворяет условию^[17]:

{h(x)}\equiv c_{i}\equiv c_{i}^{q}\equiv h(x)^{q}{\pmod {f_{i}(x)}},\quad i={\overline {1,\;k}}

,

и поэтому^[18]:

h(x)^{q}\equiv h(x){\pmod {f(x)}},\quad \deg {h(x)}<deg{f(x)}

.

Из условия:

h(x)^{q}-h(x)=\prod _{c\in \mathbb {F} _{q}}(h(x)-c)\equiv 0{\pmod {f(x)}}

,

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

f(x)=\prod _{c\in \mathbb {F} _{q}}\gcd(f(x),h(x)-c).

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

h(x)=a_{0}+a_{1}x^{1}+\dots +a_{n-1}x^{n-1}\in \mathbb {F} _{q}

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

h(x)^{q}\equiv h(x){\pmod {f(x)}}

,

которое равносильно условию^[17]:

\sum _{i=0}^{n-1}a_{i}x^{iq}\equiv \sum _{i=0}^{n-1}a_{i}x^{i}{\pmod {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}

,

поэтому^[17]:

\sum _{i=0}^{n-1}a_{i}b_{ij}=a_{j},\quad j={\overline {0,\;n-1}}

.

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

\quad (a_{0},\;a_{1},...,a_{n-1})B=(a_{0},\;a_{1},\;...,a_{n-1})

или:

\quad (a_{0},\;a_{1},...,a_{n-1})(B-E_{n})=\mathbf {0}

^[17].

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

Сложность алгоритма составляет $O(n^{3}+qkn)$ математических операций^[19]. Алгоритм будет эффективен только для небольших полей. Это связано с необходимостью перебора всех $c\in \mathbb {F} _{q}$ .

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

В случае простого поля, если значение $p$ велико, то перебор значений $c\in {\mathbb {Z} /p\mathbb {Z} }$ займёт много времени. Однако, возможно определить множество $M$ , состоящее из $c$ , для которых $\gcd(f(x),h(x)-c)$ нетривиален^[20]. Для этого необходимо найти корни результанта^[21] $R(c)$ , которые и будут составлять множество $M$ .
Ещё один метод разложения унитарного многочлена $f(x)\in GF(q)[x]$ , не имеющего кратных неприводимых множителей, основан на приведении некоторой эффективно вычислимой с помощью алгоритма Берлекэмпа матрицы A к диагональному виду^[22]. Однако сам процесс диагонализации довольно сложен.
В работе Калтофена и Лобо^[23] была предложена вероятностная версия алгоритма Берлекэмпа, позволяющая разложить на множители многочлен $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.

Применение

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

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

В системе компьютерной алгебры PARI/GP^[англ.] алгоритм Берлекэмпа может быть использован посредством команды factormod^[26].

Примечания

↑ Berlekamp, 1967, с. 1854: «О циклических кодах».
↑ ¹ ² Berlekamp, 1967.
↑ Berlekamp, 1967, с. 1853.
↑ Голомб, Соломон Вольф. Shift Register Sequences. — Aegean Park Pr; Revised edition, 1981. — 274 с. — ISBN 978-0894120480. Архивировано 26 августа 2016 года.
↑ PETR K. Uber die Reduzibilitat eines Polynoms mit ganzzahligen Koeffi-zienten nach einem Primzahlmodul. — Casopis Pest Mat. Fys, 1937. — С. 85—94.
↑ Butler, M. C. R. On the reducibility of polynomials over a finite field. — The Quarterly Journal of Mathematics Oxford Second Series 5, 1954. — С. 102—107.
↑ Schwarz, St. On the reducibility of polynomials over a ﬁnite ﬁeld. — Quart. J. Math. Oxford Ser.(2) 7, 1956. — С. 110—124.
↑ Лидл, 1988, Исторические комментарии, с. 223-224.
↑ Cantor D.G., Zassenhaus H. A new algorithm for factoring polynomials over finite fields. — Math. Comp., 1981. — Vol. 36. — P. 587—592.
↑ von zur Gathen J., Shoup V. Computing Frobenius maps and factoring polynomials. — Comput. Complexity, 1992. — Т. 2. — С. 187—224.
↑ Василенко, 2003, с. 185: «Сложность алгоритма Кантора—Цассенхауза».
↑ Лидл, 1988, Постановка задачи, с. 187.
↑ Василенко, 2003, Определения, с. 172.
↑ ¹ ² Василенко, 2003, Описание алгоритма, с. 173.
↑ ¹ ² ³ ⁴ Лидл, 1988, Описание алгоритма.
↑ ¹ ² ³ ⁴ Лидл, 1988, Сведение к основному случаю, с. 188.
↑ ¹ ² ³ ⁴ ⁵ Лидл, 1988, Обоснование корректности алгоритма, с. 189-190.
↑ ¹ ² Василенко, 2003, с. 174.
↑ Василенко, 2003, с. 174: «Сложность алгоритма».
↑ Лидл, 1988, Подробнее о методе, с. 201.
↑ Ван дер Варден, 1976, О результанте, с. 124.
↑ Лидл, 1988, Подробнее о методе, с. 206.
↑ Kaltofen E, Lobo A. Factoring high-degree polynomials by the black box Berlekamp algorithm (англ.) // Proceedings of the international symposium on Symbolic and algebraic computation (ISSAC ’94). — N. Y.: ACM Press, 1994. — P. 90—98. — ISBN 0-89791-638-7. — doi:10.1145/190347.190371.
↑ Лидл, 1988, Применение алгоритма, с. 187.
↑ Василенко, 2003, Об использовании алгоритмов с факторными базами для решения задачи дискретного логарифмирования, с. 137.
↑ Catalogue of GP/PARI Functions: Arithmetic functions Архивировано 11 марта 2007 года.

Литература

Berlekamp, Elwyn R. Factoring Polynomials Over Finite Fields (англ.) // Bell System Technical Journal^[англ.]. — 1967. — Vol. 46. — P. 1853—1859. BSTJ Later republished in: Berlekamp, Elwyn R. Algebraic Coding Theory (англ.). — McGraw-Hill Education, 1968. — ISBN 0-89412-063-8.
Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4.
Лидл Р., Нидеррайтер Г. Конечные поля = Finite Fields / Под ред. В. И. Нечаева. — 1-е изд. — М.: Мир, 1988. — Т. 1. — 430 с. — ISBN 5-03-000065-8.
Ван дер Варден Б.Л. Алгебра. — M.: Наука, 1976. — 646 с. Архивная копия от 2 ноября 2013 на Wayback Machine

[_17887290c5981922-1] Berlekamp, 1967, с. 1854: «О циклических кодах».

[_722d7cd7ff7cd253-2] ¹ ² Berlekamp, 1967.

[_de0e5a0fb3a9414c-3] Berlekamp, 1967, с. 1853.

[4] Голомб, Соломон Вольф. Shift Register Sequences. — Aegean Park Pr; Revised edition, 1981. — 274 с. — ISBN 978-0894120480. Архивировано 26 августа 2016 года.

[5] PETR K. Uber die Reduzibilitat eines Polynoms mit ganzzahligen Koeffi-zienten nach einem Primzahlmodul. — Casopis Pest Mat. Fys, 1937. — С. 85—94.

[6] Butler, M. C. R. On the reducibility of polynomials over a finite field. — The Quarterly Journal of Mathematics Oxford Second Series 5, 1954. — С. 102—107.

[7] Schwarz, St. On the reducibility of polynomials over a ﬁnite ﬁeld. — Quart. J. Math. Oxford Ser.(2) 7, 1956. — С. 110—124.

[_d95e3b66a324a0ff-8] Лидл, 1988, Исторические комментарии, с. 223-224.

[9] Cantor D.G., Zassenhaus H. A new algorithm for factoring polynomials over finite fields. — Math. Comp., 1981. — Vol. 36. — P. 587—592.

[10] von zur Gathen J., Shoup V. Computing Frobenius maps and factoring polynomials. — Comput. Complexity, 1992. — Т. 2. — С. 187—224.

[_e39576774933bd6e-11] Василенко, 2003, с. 185: «Сложность алгоритма Кантора—Цассенхауза».

[_312ec990cc0ecdc5-12] Лидл, 1988, Постановка задачи, с. 187.

[_126dbe6b174abc38-13] Василенко, 2003, Определения, с. 172.

[_8e770f3003a9165b-14] ¹ ² Василенко, 2003, Описание алгоритма, с. 173.

[_2ef9bd91a39fcafe-15] ¹ ² ³ ⁴ Лидл, 1988, Описание алгоритма.

[_6322e606a87f9cdb-16] ¹ ² ³ ⁴ Лидл, 1988, Сведение к основному случаю, с. 188.

[_cb0385ea89c8b268-17] ¹ ² ³ ⁴ ⁵ Лидл, 1988, Обоснование корректности алгоритма, с. 189-190.

[_77297e1f27db1113-18] ¹ ² Василенко, 2003, с. 174.

[_6330aa0b7f960dea-19] Василенко, 2003, с. 174: «Сложность алгоритма».

[_3b3c12ed34c3016f-20] Лидл, 1988, Подробнее о методе, с. 201.

[_9ccfaae51d4c6738-21] Ван дер Варден, 1976, О результанте, с. 124.

[_3b3c12ed34c30168-22] Лидл, 1988, Подробнее о методе, с. 206.

[23] Kaltofen E, Lobo A. Factoring high-degree polynomials by the black box Berlekamp algorithm (англ.) // Proceedings of the international symposium on Symbolic and algebraic computation (ISSAC ’94). — N. Y.: ACM Press, 1994. — P. 90—98. — ISBN 0-89791-638-7. — doi:10.1145/190347.190371.

[_32405416c34be5ea-24] Лидл, 1988, Применение алгоритма, с. 187.

[_222a47d267ec21a0-25] Василенко, 2003, Об использовании алгоритмов с факторными базами для решения задачи дискретного логарифмирования, с. 137.

[26] Catalogue of GP/PARI Functions: Arithmetic functions Архивировано 11 марта 2007 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]