Алгоритм Берлекэмпа
Алгоритм Берлекэмпа — алгоритм, предназначенный для факторизации унитарных многочленов над конечным полем. Разработан Элвином Берлекэмпом в 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].
Основной случай
[править | править код]Алгоритм факторизации над конечным полем многочлена вида:
состоит из следующих шагов:
- Вычисление матрицы [14].
- Поиск базиса подпространства решений системы линейных уравнений[15]:
- ,
- при этом удаётся выбрать вектор , так как он всегда будет присутствовать[15] в базисе пространства решений ввиду того, что при .
- Найденное число есть число неприводимых делителей[14] .
- Если , то многочлен является неприводимым.
- Если , то векторы имеют вид . По этим числам строятся -разлагающие многочлены:
- .
- Поиск разложения[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[англ.] алгоритм Берлекэмпа может быть использован посредством команды factormod
[26].
Примечания
[править | править код]- ↑ Berlekamp, 1967, с. 1854: «О циклических кодах».
- ↑ 1 2 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 finite field. — 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.
- ↑ 1 2 Василенко, 2003, Описание алгоритма, с. 173.
- ↑ 1 2 3 4 Лидл, 1988, Описание алгоритма.
- ↑ 1 2 3 4 Лидл, 1988, Сведение к основному случаю, с. 188.
- ↑ 1 2 3 4 5 Лидл, 1988, Обоснование корректности алгоритма, с. 189-190.
- ↑ 1 2 Василенко, 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