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

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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Алгоритм Берлекампа»)
Перейти к: навигация, поиск

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

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

История создания[править | править вики-текст]

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

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

Алгоритм Берлекэмпа упоминался во множестве работ[8] и являлся основным алгоритмом решения проблемы факторизации до появления в 1981 году алгоритма Кантора — Цассенхауза (англ.)[9]. Была разработанна техника[10] позволяющая разложить многочлен на множители за где  — показатель в оценке сложности перемножения квадратных матриц[11].

Постановка и определения[править | править вики-текст]

Рассматривается задача факторизации многочлена степени () над конечным полем (,  — простое число)[12] на различные неприводимые унитарные многочлены .

Для использования в алгоритме строится матрица согласно следующим условиям:

.

Многочлен такой, что , называется -разлагающим многочленом[13].

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

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

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

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

  1. Вычисление матрицы [14].
  2. Поиск базиса подпространства решений системы линейных уравнений[15]:
    ,
    при этом удаётся выбрать вектор , так как он всегда будет присутствовать[15] в базисе пространства решений ввиду того, что при .
  3. Найденное число есть число неприводимых делителей[14] .
    • Если , то многочлен является неприводимым.
    • Если , то вектора имеют вид . По этим числам строятся -разлагающие многочлены:
      .
  4. Поиск разложения[15]:
    в виде:
    ,
    где в общем случае не являются неприводимыми. Функции факторизуются таким же способом[15], то есть:
    .

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

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

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

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

  • Если то многочлен не содержит кратных корней, так как кратный корень одновременно является и корнем производной[16].
  • Если то и значит Если то для необходимо проделать описанную процедуру до тех пор пока не будет получено разложение Многочлен удовлетворяет требованиям основного случая[16].
  • Иначе, многочлен является нетривиальным делителем многочлена . В свою очередь, многочлен не имеет кратных неприводимых сомножителей[16]. Если содержит кратные сомножители, то к нему также применяется описанная процедура. Зная эти разложения, легко получить разложение .

Таким образом, задача разложения произвольного унитарного многочлена над конечным полем сводится к разложению на множители конечного числа многочленов, которые не имеют кратных неприводимых сомножителей, то есть к основному случаю[16].

Обоснование[править | править вики-текст]

Пусть:

, где .

Согласно китайской теореме об остатках существует единственный многочлен для любого набора элементов поля [17]:

такой что:

.

Многочлен удовлетворяет условию[17]:

,

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

.

Из условия:

,

и из взаимной простоты сомножителей в правой части следует, что каждый неприводимый делитель многочлена делит один, и только один из многочленов . Таким образом, доказана справедливость и единственность разложения[18]:

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

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

,

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

.

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

,

поэтому[17]:

.

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

или:

[17].

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

Сложность алгоритма составляет математических операций[19]. Алгоритм будет эффективен только для небольших полей. Это связанно с необходимостью перебора всех .

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

  • В случае простого поля, если значение велико, то перебор значений займёт много времени. Однако, возможно определить множество , состоящее из , для которых нетривиален[20]. Для этого необходимо найти корни результанта[21] , которые и будут составлять множество .
  • Ещё один метод разложения унитарного многочлена , не имеющего кратных неприводимых множителей, основан на приведении некоторой эффективно вычислимой с помощью алгоритма Берлекэмпа матрицы A к диагональному виду[22]. Однако сам процесс диагонализации довольно сложен.
  • В работе Калтофена и Лобо[23] была предложена вероятностная версия алгоритма Берлекэмпа, позволяющая разложить на множители многочлен степени за арифметических операций. Алгоритм Калтофена — Лобо был реализован на компьютере, и оказался эффективным для многочленов высокой степени, например, для многочленов степени 10001 над полем он работает около 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, Исторические комментарии, с. 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.
  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, с. 174: «Сложность алгоритма».
  20. Лидл, 1988, Подробнее о методе, с. 201.
  21. Ван дер Варден, 1976, О результанте, с. 124.
  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.
  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 с.