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

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

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

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

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

Алгоритм Берлекэмпа упоминался во множестве работ и являлся основным алгоритмом решения проблемы факторизации до появления в 1981 году . Была разработана техника позволяющая разложить многочлен на множители за где  — показатель в оценке сложности перемножения квадратных матриц.

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

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

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

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

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

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

в виде: , где в общем случае не являются неприводимыми. Функции факторизуются таким же способом, то есть: .

Общий случай

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

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

Обоснование Пусть: , где . Согласно китайской теореме об остатках существует единственный многочлен для любого набора элементов поля :

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

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

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

или: .

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

Усовершенствования В случае простого поля, если значение велико, то перебор значений займёт много времени. Однако, возможно определить множество , состоящее из , для которых нетривиален. Для этого необходимо найти корни результанта , которые и будут составлять множество . Ещё один метод разложения унитарного многочлена , не имеющего кратных неприводимых множителей, основан на приведении некоторой эффективно вычислимой с помощью алгоритма Берлекэмпа матрицы A к диагональному виду. Однако сам процесс диагонализации довольно сложен. В работе Калтофена и Лобо была предложена вероятностная версия алгоритма Берлекэмпа, позволяющая разложить на множители многочлен степени за арифметических операций. Алгоритм Калтофена — Лобо был реализован на компьютере, и оказался эффективным для многочленов высокой степени, например, для многочленов степени 10001 над полем он работает около 102,5 часов на компьютере Sun-4.

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

Реализации в системах компьютерной алгебры В системе компьютерной алгебры алгоритм Берлекэмпа может быть использован посредством команды factormodCatalogue of GP/PARI Functions: Arithmetic functions .

Примечания

Литература BSTJ Later republished in:

Категория:Вычислительная алгебра Категория:Алгоритмы