Эта статья входит в число хороших статей

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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Берлекэмпа — алгоритм, предназначенный для факторизации унитарных многочленов над конечным полем. Разработан Элвином Берлекэмпом (англ.)русск. в 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 \ge 2) над конечным полем \Bbb{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^i}^q \equiv \sum^{n-1}_{j=0} b_{ij} x^i \pmod{f(x)}\quad i=\overline{1,n-1}.

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

Основной случай[править | править вики-текст]

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

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

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

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

  1. Вычисление матрицы B[14].
  2. Поиск базиса \overline{e_1},\dots ,\overline{e_k} подпространства решений системы линейных уравнений[15]:
    (B-E_n)^T \bold x = \bold 0,
    при этом удаётся выбрать вектор \overline{e_1} = (1,\;0,\;....\;,\;0), так как он всегда будет присутствовать[15] в базисе пространства решений ввиду того, что {x^i}^q \equiv 1\pmod{f(x)} при i=0.
  3. Найденное число k есть число неприводимых делителей[14] f(x).
    • Если k=1, то многочлен является неприводимым.
    • Если k>1, то компонентами векторов \overline{e_l} являются числа (h_{l,\;0}, \dots , h_{l,\;n-1}). По этим числам строятся f-разлагающие многочлены:
      h_l(x) = \sum^{n-1}_{i=0} h_{l,\;i}\;x_i, \quad l=\overline{2,\;k}.
  4. Поиск разложения[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 \Bbb{F}_q [x]. Если g^{'}(x) = 0, то для g(x) необходимо проделать описанную процедуру до тех пор пока не будет получено разложение f(x) = h(x)^{p^s}, h{'}(x) \ne 0. Многочлен h(x) удовлетворяет требованиям основного случая[16].
  • Иначе, многочлен d(x) является нетривиальным делителем многочлена f(x). В свою очередь, многочлен \frac{f(x)}{d(x)} не имеет кратных неприводимых сомножителей[16]. Если d(x) содержит кратные сомножители, то к нему также применяется описанная процедура. Зная эти разложения, легко получить разложение f(x).

Таким образом, задача разложения произвольного унитарного многочлена над конечным полем  \Bbb{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_1x^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_ix^{iq}\equiv\sum_{i=0}^{n-1}a_ix^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_ix^i,

поэтому[17]:

\sum_{i=0}^{n-1}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)=\bold0[17].

Сложность алгоритма[править | править вики-текст]

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

Усовершенствования[править | править вики-текст]

  • В случае простого поля, если значение p велико, то перебор значений c \in {\Bbb{Z} / p \Bbb{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 над полем \Bbb{Z}/127\Bbb{Z} он работает около 102,5 часов на компьютере Sun-4.

Применение[править | править вики-текст]

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

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

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

Примечания[править | править вики-текст]

  1. Berlekamp, 1967, с. 1854: «О циклических кодах»
  2. 1 2 Berlekamp, 1967
  3. Berlekamp, 1967, с. 1853
  4. Голомб, Соломон Вольф Shift Register Sequences. — Aegean Park Pr; Revised edition, 1981. — 274 с. — ISBN 978-0894120480.
  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 finite field. — Quart. J. Math. Oxford Ser.(2) 7, 1956. — С. 110-124.
  8. Лидл, 1988, Исторические комментарии
  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.
  11. Василенко, 2003, с. 185: «Сложность алгоритма Кантора—Цассенхауза»
  12. Лидл, 1988, Постановка задачи, с. 187
  13. Василенко, 2003, Определения, с. 172
  14. 1 2 Василенко, 2003, Описание алгоритма, с. 173
  15. 1 2 3 4 Лидл, 1988, Описание алгоритма
  16. 1 2 3 4 Лидл, 1988, Сведение к основному случаю, с. 188
  17. 1 2 3 4 5 Лидл, 1988, Обоснование корректности алгоритма, с. 189-190
  18. 1 2 Василенко, 2003, с. 174
  19. Василенко, 2003: «Сложность алгоритма»
  20. Лидл, 1988, Подробнее о методе, с. 201
  21. Ван дер Варден, 1976, О результанте, с. 124
  22. Лидл, 1988, Подробнее о методе
  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. — С. 90—98. — ISBN 0-89791-638-7. — DOI:10.1145/190347.190371
  24. Лидл, 1988, Применение алгоритма, с. 187
  25. Василенко, 2003, Об использовании алгоритмов с факторными базами для решения задачи дискретного логарифмирования, с. 137
  26. Catalogue of GP/PARI Functions: Arithmetic functions

Литература[править | править вики-текст]

  • Лидл Р., Нидеррайтер Г. Конечные поля = Finite Fields / Под ред. В. И. Нечаева. — 1-е изд. — М.: Мир, 1988. — Т. 1. — 430 с. — ISBN 5-03-000065-8.
  • Ван дер Варден Б.Л. Алгебра. — M.: Наука, 1976. — 646 с.